[백준] 4803 트리 c++

https://www.acmicpc.net/problem/4803 

4803번: 트리

 

풀이과정

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

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

만약 사이클이 존재한다면 넘어가주고, 사이클이 존재하지 않으며 부모 노드의 카운트가 한 번이라도 되지 않은 경우에는 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;
}