deliciousqoo   2년 전

안녕하세요 

4803 문제 풀다가 제 나름 테스트케이스라고 생각하고 풀다가 의문이 생겼습니다


다음과 같은  테스트케이스는 안되나요?

같은 간선이 없고 저 경우에는 트리가 없어야 한다고 생각하는데

정답코드로 실행하면 트리가 하나 있다고 나오네요


제 생각이 틀린건지 문제가 틀린건지 알려주시면 감사하겠습니다!

nflight11   2년 전

트리가 하나 있는 것이 맞습니다.

이 테스트케이스는 세 개의 정점이 1-2-3 형태로 연결되어 있는 것이고, 이는 사이클이 없는 연결요소를 1-2-3 하나 가지므로 트리가 하나 있게 됩니다.

deliciousqoo   2년 전

사이클이 없는 조건을 만족하면 트리가 되는거였군요!

제가 잘 몰라서그런데 혹시 하나의 정점이 두개이상의 부모노드를 가져도 괜찮은건가요?

nflight11   2년 전

정점이 루트가 아닌 이상 루트가 아닌 이상 하나의 정점은 반드시 하나의 부모를 가집니다.

하지만 트리의 부모자식 관계는 루트가 무엇인지에 따라 결정되며, 문제에서 간선을 a b라고 주었다 할지라도 a가 부모, b가 자식(혹은 그 반대)이라는 보장은 없습니다.

예를 들어서 1-2-3 형태의 트리에서 1이 루트면 2의 부모가 1, 3의 부모가 2가 되지만 2가 루트라면 1과 3 모두 2를 부모로 가집니다.

deliciousqoo   2년 전

친절한 답변 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.