总时间限制: 

5000ms

 

内存限制: 

65536kB

描述

世界上有许多宗教，你感兴趣的是你学校里的同学信仰多少种宗教。

你的学校有n名学生（0 < n <= 50000），你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。但是当你同时找到2名学生，他们却愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。

 

输入

输入包括多组数据。
每组数据的第一行包括n和m，0 <= m <= n(n-1)/2，其后m行每行包括两个数字i和j，表示学生i和学生j信仰同一宗教，学生被标号为1至n。输入以一行 n = m = 0 作为结束。

输出

对于每组数据，先输出它的编号（从1开始），接着输出学生信仰的不同宗教的数目上限。

样例输入

10 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0

样例输出

Case 1: 1Case 2: 7

第一眼：Tarjan
第二眼：刚刚眼瞎，，并查集带走

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=50001; 7 void read(int &n) 8 { 9     char c=‘+‘;int x=0;bool flag=0;10     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}11     while(c>=‘0‘&&c<=‘9‘)12     x=(x<<1)+(x<<3)+c-48,c=getchar();13     flag==1?n=-x:n=x;14 }15 int n,m;16 int fa[MAXN];17 bool vis[MAXN];18 int find(int x)19 {20     if(fa[x]==x)21         return fa[x];22     return fa[x]=find(fa[x]);23 }24 void unionn(int x,int y)25 {26     int fx=find(x);27     int fy=find(y);28     fa[fx]=fy;29 }30 int tot=0;31 int main()32 {33     while(scanf("%d%d",&n,&m))34     {35         if(n==0&&m==0)break;36         for(int i=1;i<=n;i++)37             fa[i]=i;38         memset(vis,0,sizeof(vis));39         40         for(int i=1;i<=m;i++)41         {42             int x,y;43             read(x);read(y);44             if(find(x)!=find(y))45                 unionn(x,y);46         }47         int ans=0;48         for(int i=1;i<=n;i++)49         {50             if(vis[find(i)]==0)51             {52                 vis[find(i)]=1;53                 ans++;54             }55         }56         printf("Case %d: %d\n",++tot,ans);57     }58     return 0;59 } 

 

02:宗教信仰