4803 트리

포레스트에서 서브 트리의 개수를 구하는 문제이다.

분리 집합 사용해서 풀었다.

 

테스트 케이스가 여러개이니 초기화에 주의할 것.

#include <iostream>
using namespace std;
int n=1,m=1;
int p[501];int height[501];bool cycle[501];
int find(int x){
	if(p[x]==-1) return x;
	return p[x]=find(p[x]);
}
void Union(int u,int v){
	u=find(u);v=find(v);
	if(u==v) {cycle[u]=true;return;} //cycle
	if(height[u]<height[v]) swap(u,v);
	cycle[u]=cycle[u]||cycle[v];
	p[v]=u;
	if(height[u]==height[v]) height[u]++;
	return ;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int k=0;
	while(true){
		k++;
		cin>>n>>m;
		if(n==0&&m==0) break;
		for(int i=0;i<=n;i++) {p[i]=-1;height[i]=0;cycle[i]=false;}
		while(m--){
			int x,y;
			cin>>x>>y;
			Union(x,y);
		}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!cycle[i]&&p[i]==-1) {ans++;}
	}
	if(ans==0) cout<<"Case "<<k<<": No trees.\n";
	else if(ans==1) cout<<"Case "<<k<<": There is one tree.\n";
	else {
		cout<<"Case "<<k<<": A forest of "<<ans<<" trees.\n";
	}
	}
	return 0;
}