[BOJ] 4803 : 트리

1717 : 집합의 표현

문제

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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."를 테스트 케이스 번호와 함께 출력한다.

풀이

이전 문제와 같이 Union-Find 를 활용하여 풀 수 있었다.

단, 이번 문제에서는 사이클인 경우를 제외해야 하기 때문에
Union 과정에서 이미 같은 집합에 속해있다면 해당 부분은 0으로 처리해준다.

m 번의 Union 연산을 끝낸 다음, 본인과 연결되어 있는 (v[i] == i) 트리의 개수를 찾으면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <set>
using namespace std;

int n, m;
vector<int> v;

int Find(int a)
{
	if (v[a] == a)
		return a;

	return v[a] = Find(v[a]);
}

void Union(int a, int b)
{
	int parent_a = Find(a);
	int parent_b = Find(b);

	if (parent_a > parent_b)
		v[parent_a] = parent_b;
	else if (parent_a < parent_b)
		v[parent_b] = parent_a;
	else
	{
		v[parent_a] = 0;
		v[parent_b] = 0;
	}
}

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

	int t = 1;
	while (1)
	{
		cin >> n >> m;

		if (n == 0 && m == 0)
			break;

		v.resize(n + 1);

		for (int i = 1; i <= n; ++i)
			v[i] = i;

		int a, b;
		for (int i = 0; i < m; ++i)
		{
			cin >> a >> b;
			Union(a, b);
		}

		int answer = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (v[i] == i)
				answer++;
		}

		cout << "Case " << t++ << ": ";

		if (answer == 1)
			cout << "There is one tree." << '\n';
		else if (answer > 1)
			cout << "A forest of " << answer << " trees." << '\n';
		else
			cout << "No trees." << '\n';


	}
	return 0;
}