백준 4803번 트리

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : DFS

(1) 코드 8~18

 DFS 탐색을 통해 Tree 인지 판별하는 함수를 하나 만들어 줍니다.

(2) 코드 35~37

 아직 탐색되지 않은 노드가 있는 경우, 해당 노드를 root로 하는 tree를 과정(1) 에서 만든 함수로 만들어 주고, tree가 만들어 졌다면, 정답+1 해줍니다.