<span>POJ 1611---The Suspects(并查集)</span>
题意：0疑似有传染病，和0在一起的都疑似被传染（这些人也会传染别人），求有多少个人可能有传染病；
直接代码＋注释（16ms）
方法1：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 6 const int maxn=20000000; 7 int par[maxn],m,n; 8 9 int find(int x) 10 { 11 if(x!=par[x]) 12 par[x]=find(par[x]); 13 return par[x]; 14 } 15 16 void unionn(int a,int b) 17 { 18 int fa=find(a); 19 int fb=find(b); 20 if(par[fb]!=fb) par[fa]=fb; //如果fb不是头 fa并入fb即头为fb 21 else par[fb]=fa; //如果fb是头 fb并入fa 22 } 23 24 int main() 25 { 26 while(scanf("%d%d",&n,&m)&&(m||n)){ 27 int p,a,b; 28 for(int i=0;i<=n;i++){ 29 par[i]=i; //每个人的头为自己 30 } 31 while(m--){ 32 scanf("%d",&p); 33 p--; 34 scanf("%d",&a); 35 for(int i=0;i<p;i++){ 36 scanf("%d",&b); 37 unionn(a,b); //a后边的所有元素都并入a即a为头 38 } 39 } 40 int sum=0; 41 for(int i=0;i<n;i++){ 42 while (par[i]!=i&&par[i]!=par[par[i]]) //如果i不是头并且i的上一级也不是头 找i的头 par[i]=头 43 par[i]=par[par[i]]; 44 } 45 for(int i=0;i<n;i++){ 46 if(par[i]==par[0]) sum++; //谁和0是同一个头 说明被传染 47 } 48 printf("%d\n",sum); 49 } 50 return 0; 51 }
方法二：（方法二和方法一意思差不多，就是更简洁了一些）
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 6 const int maxn=300100; 7 int par[maxn],m,n; 8 9 int find(int x) 10 { 11 if(x!=par[x]) 12 par[x]=find(par[x]); 13 return par[x]; 14 } 15 16 void unionn(int a,int b) 17 { 18 int fa=find(a); 19 int fb=find(b); 20 if(fa==fb) return; 21 else par[fb]=fa; 22 } 23 24 int main() 25 { 26 while(scanf("%d%d",&n,&m)&&(m||n)){ 27 int p,a,b; 28 for(int i=0;i<=n;i++){ 29 par[i]=i; 30 } 31 while(m--){ 32 scanf("%d",&p); 33 p--; 34 scanf("%d",&a); 35 for(int i=0;i<p;i++){ 36 scanf("%d",&b); 37 unionn(a,b); 38 } 39 } 40 int sum=0; 41 for(int i=0;i<n;i++){ 42 if(find(i)==find(0)) sum++; 43 } 44 printf("%d\n",sum); 45 } 46 return 0; 47 }
国家电网工作强度 101人发布
