[백준] 4803 트리 c++

문제 링크 https://www.acmicpc.net/problem/4803

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

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

풀이 과정

기본 문제인 것 같았지만, 생각해야될 것이 많았던 문제이다.
입력을 받고 나서, 두 노드의 부모가 다른 집합일 때와 같은 집합일 때로 나눈다.

다른 집합일 때는 부모의 노드를 통일시켜주고, 만약에 두 부모 중 한 집합이라도 사이클이 존재한다면 두 집합 모두 사이클로 변경해준다.
같은 집합일 때는 시작 노드를 사이클로 변경해준다.

만약 사이클이 존재한다면 넘어가주고, 사이클이 존재하지 않으며 부모 노드의 카운트가 한 번이라도 되지 않은 경우에는 res를 +1 해준다. 이 부분은 visited배열 느낌과 같다고 생각하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n, m, x, y, parent[501];
bool cycle[501];

int getParent(int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent[x]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int tc = 1;
	while (1) {
		int cnt = 0;
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
			cycle[i] = false;
		}
		for (int i = 0; i < m; i++) {
			cin >> x >> y;
			int start = getParent(x);
			int end = getParent(y);

			if (start != end) { // 다른 집합
				if (cycle[start] || cycle[end]) {
					cycle[start] = cycle[end] = true;
				}
				parent[end] = start;
			}
			else { // 같은 집합
				cycle[start] = true;
			}
		}

		map <int, int> m;
		int res = 0;
		for (int i = 1; i <= n; i++) {
			int x = getParent(i);
			if (cycle[x]) continue;
			if (m.count(x) == 0) {
				m[x] = 1;
				res++;
			}
		}
		cout << "Case " << tc; tc++;
		if (res == 0) cout << ": No trees.\n";
		else if (res == 1) cout << ": There is one tree.\n";
		else if (res > 1) cout << ": A forest of " << res << " trees.\n";
	}
	return 0;
}