이 문제는 주어진 테스트 케이스 당 정점의 개수와 간선 정보를 기반으로 만들어지는 그룹 중 트리구조의 그룹의 개수를 반환하면 되는 문제이다.
이 문제를 읽자마자 유니온 파인드 알고리즘이 떠올랐다.
처음 주어지는 정점의 개수만큼 리스트를 생성하고 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++;
}
}