POJ 1611---The Suspects(并查集)

60 阅读 0 评论 40 点赞

我是靠谱客的博主威武小丸子，最近开发中收集的这篇文章主要介绍POJ 1611---The Suspects(并查集)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：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("%dn",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("%dn",sum);
45     }
46     return 0;
47 }