skynet   6년 전

1. 제가 틀렸던 부분: 

여러개의 유니온중에서 1개라도 그래프가 있으면 "No trees." 를 출력하는 것이 아닙니다.

그냥 카운트에 포함되지 않을 뿐입니다.


2. 기타 다른 질문들

*루트노드가 정해져 있지 않습니다.*

a -> b로 갈수 있다면

b -> a 도 가능합니다.

또한 a -> a 도 가능 합니다. ( 길이가 1인 싸이클)


3. 개략적인 풀이 방법

유니온 시켜서 트리 개수 세면 됩니다.

저같은 경우에는 bfs 탐색을 하면서 다시 발견한 곳을 재방문 했는데, 재방문 한곳이 해당 노드의 부모 노드가 아닐 경우 flag를 주고 연결된 노드들을 모두 체크한 후, 카운터를 증가 시키지 않았습니다.

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