[ICPC] 백준 4803 - 트리

[ICPC] 백준 4803 - 트리

주어진 포레스트에서 트리의 개수를 찾는 문제이다.

포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다.

각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다.

노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다.

전체 코드 - 유니온 파인드로 구현했다.

from http://nicotina04.tistory.com/158 by ccl(A) rewrite - 2021-08-24 23:00:08