[백준] 4803 트리

정태호·2022년 11월 25일
0

이 문제는 주어진 테스트 케이스 당 정점의 개수와 간선 정보를 기반으로 만들어지는 그룹 중 트리구조의 그룹의 개수를 반환하면 되는 문제이다.

이 문제를 읽자마자 유니온 파인드 알고리즘이 떠올랐다.
처음 주어지는 정점의 개수만큼 리스트를 생성하고 0으로 초기화 한 후, 입력되는 간선 정보를 통해 리스트 정보를 갱신해 나간다.
모든 간선에 대한 처리가 끝난 후, 리스트에서 0을 담고 있는 개수가 그룹의 개수가 된다.

단, 이 그룹에서 그래프 요소를 가지는 그룹이 존재할 수 있고 이를 구분할 수 있어야 한다.
구분하기 위해 그룹정보가 동일한 간선정보가 들어왔을 경우 이를 -1로 마킹한다.
이후 다른 그룹간의 합치는 과정중 -1을 가진 root 그룹이 우선순위를 가지도록 하여 그래프 그룹과 트리 그룹을 구분할 수 있다.

#include<iostream>
#include<vector>

using namespace std;

int n, m;
int edge[501];

int find(int n) {
	if (edge[n] <= 0)
		return n;
	return edge[n] = find(edge[n]);
}

int main() {
	int case_num = 1;
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		fill(edge, edge + n + 1, 0);
		int a, b;

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

			int A = find(a);
			int B = find(b);
			if (A != B) {
				if (edge[A] == -1) edge[B] = A;
				else if (edge[B] == -1) edge[A] = B;
				else edge[A] = B;
			}
			else {
				edge[A] = -1;
			}
		}
		int forest = 0;
		for (int i = 1; i <= n; i++) {
			if (edge[i] == 0) forest++;
		}
		if (forest == 0) cout << "Case "<<case_num <<": No trees.\n";
		else if (forest == 1) cout << "Case "<<case_num<<": There is one tree.\n";
		else cout << "Case "<< case_num<<": A forest of " << forest << " trees.\n";
		case_num++;
	}
}

0개의 댓글