[백준] 4803번 트리 C++

4803번: 트리 문제 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테... www.acmicpc.net 이렇게 많이 틀리면 알고리즘 너무 하기 싫어~ 유니온 파인드 이용해서 풀었다. 근데 뭔가 좋은 풀이는 아닌 것 같긴 한데 ㅎ 먼저 dfs 돌려서 연결된 점들을 방문해 준다. 그리고 다시 union-find 돌려서 사이클이 있는지 판단해 준다. dfs를 먼저 돌리는 이유는 1 1 1 2 2 3 과 같은 경...

원문링크 : [백준] 4803번 트리 C++