백준 4803. 트리

tose33 2022. 10. 31. 16:56

4803번: 트리

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

www.acmicpc.net

union-find 알고리즘으로 (크루스칼 알고리즘에서 그래프가 싸이클을 이루는지 확인 하는 것처럼) 싸이클이 있는지 없는지 판단하면 된다.

싸이클이 있다면 해당 노드부터 dfs로 연결된 노드들은 모두 그래프라고 표시한다.

마지막으로 그래프가 아닌 노드들을 순회하면서 몇개의 트리로 이루어 졌는지 확인하면 된다.

싸이클 이라는 말 때문에 mst -> 크루스칼 -> union-find 를 떠올리긴 했는데

사실 이 문제는 이렇게 하지 말고 그냥 노드들 순회하면서 방문한 정점을 다시 방문했으면 그래프 아니면 트리라고 계산해주면 됐을것 같다.