總時(shí)間限制:?

5000ms

內(nèi)存限制:?

65536kB

描述

世界上有許多宗教，你感興趣的是你學(xué)校里的同學(xué)信仰多少種宗教。 你的學(xué)校有n名學(xué)生（0 < n <= 50000），你不太可能詢問(wèn)每個(gè)人的宗教信仰，因?yàn)樗麄儾惶敢馔嘎丁５钱?dāng)你同時(shí)找到2名學(xué)生，他們卻愿意告訴你他們是否信仰同一宗教，你可以通過(guò)很多這樣的詢問(wèn)估算學(xué)校里的宗教數(shù)目的上限。你可以認(rèn)為每名學(xué)生只會(huì)信仰最多一種宗教。

?

輸入

輸入包括多組數(shù)據(jù)。
每組數(shù)據(jù)的第一行包括n和m，0 <= m <= n(n-1)/2，其后m行每行包括兩個(gè)數(shù)字i和j，表示學(xué)生i和學(xué)生j信仰同一宗教，學(xué)生被標(biāo)號(hào)為1至n。輸入以一行 n = m = 0 作為結(jié)束。

輸出

對(duì)于每組數(shù)據(jù)，先輸出它的編號(hào)（從1開始），接著輸出學(xué)生信仰的不同宗教的數(shù)目上限。

樣例輸入

10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0

樣例輸出

Case 1: 1 Case 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 }

?

總結(jié)

以上是生活随笔為你收集整理的02:宗教信仰的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。