BOJ: 트리 (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."를 테스트 케이스 번호와 함께 출력한다.

 

 

트리의 정의가 곧 사이클이 없는 그래프이므로 사이클이 생성되는지를 찾아주면 된다.

두 정점이 같은 그래프에 속하면 연결했을 때 사이클이 생긴다.

같은 그래프에 속하는지 확인하는 방법은 유니온파인드

 

Find 연산

int findParent(int node) {
	if (parent[node] < 0) {
		return node;
	}
	return parent[node] = findParent(parent[node]);
}

 

Union 연산

void unionInput(int x, int y) {
	int xp = findParent(x);
	int yp = findParent(y);
	if (xp == yp) { //이미 같은 집합에 속해 있다면 사이클 발생, union하지 않음
		cycle[xp] = true;
		return;
	}
	if (cycle[xp] || cycle[yp]) { //다른 집합에 속해 있지만 하나라도 사이클이 있는 집합이면
		cycle[xp] = cycle[yp] = true;
	}
	if (parent[xp] < parent[yp]) {
		swap(xp, yp);
	}
	//집합 크기가 더 큰 쪽에다 합침
	parent[yp] += parent[xp];
	//새로운 루트 yp
	parent[xp] = yp;
}

사이클 여부를 확인하는 부분이 추가되었다

서로 다른 집합에 속해 있더라도 만약 하나라도 사이클이 있다면, union했을 때의 새로운 그래프에도 사이클이 존재하게 되므로, cycle[xp]와 cycle[yp]를 모두 true로 바꿔준다.

 

트리 개수를 세는 연산

int cntTree(int n) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (parent[i] < 0 && !cycle[i]) { //루트 정점이면서 사이클이 없음
			cnt++;
		}
	}
	return cnt;
}

유니온파인드 연산에 따르면 parent 배열에서 음수값을 갖는 정점이 루트 정점이 된다.

루트 정점이면서 사이클이 없다면 트리이므로 카운트를 늘려준다.

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;
vector<bool> cycle;

int findParent(int node) {
	if (parent[node] < 0) {
		return node;
	}
	return parent[node] = findParent(parent[node]);
}

void unionInput(int x, int y) {
	int xp = findParent(x);
	int yp = findParent(y);
	if (xp == yp) { //이미 같은 집합에 속해 있다면 사이클 발생, union하지 않음
		cycle[xp] = true;
		return;
	}
	if (cycle[xp] || cycle[yp]) { //다른 집합에 속해 있지만 하나라도 사이클이 있는 집합이면
		cycle[xp] = cycle[yp] = true;
	}
	if (parent[xp] < parent[yp]) {
		swap(xp, yp);
	}
	//집합 크기가 더 큰 쪽에다 합침
	parent[yp] += parent[xp];
	//새로운 루트 yp
	parent[xp] = yp;
}

int cntTree(int n) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (parent[i] < 0 && !cycle[i]) { //루트 정점이면서 사이클이 없음
			cnt++;
		}
	}
	return cnt;
}

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

	int n, m, a, b, num = 0;

	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		num++;
		parent.assign(n + 1, -1);
		cycle.assign(n + 1, false);
		while (m--) {
			cin >> a >> b;
			unionInput(a, b);
		}
		int ans = cntTree(n);
		cout << "Case " << num;
		switch (ans) {
		case 0:
			cout << ": No trees.\n";
			break;
		case 1:
			cout << ": There is one tree.\n";
			break;
		default:
			cout << ": A forest of " << ans << " trees.\n";
			break;
		}
	}

	return 0;
}