【并查集】模板 + 【HDU 1213、HDU 1232、POJ 2236、POJ 1703】例题详解

不想看模板，想直接看题目的请戳下面目录：

目录：

hdu 1213 how many tables【传送门】

hdu 1232 畅通工程 【传送门】

poj 2236 wireless network 【传送门】

poj 1703 find them, catch them 【传送门】

---

先上模板：

 1 #define maxn 根据编号需要
 2 int per[maxn],rank[maxn];
 3 
 4 void init(int n)
 5 {
 6     int i;
 7     for(i=1;i<=n;i++)
 8     {
 9         per[i]=i;rank[i]=0
10     }
11         
12 }
13 
14 int find(int x)
15 {
16     if(x==per[x])
17         return x;
18     return per[x]=find(per[x]);
19 }
20 
21 void unite(int x,int y)
22 {
23     x=find(x);
24     y=find(y);
25     if(x==y)
26         return;
27     if(rank[x]>rank[y])
28         per[y]=x;
29     else
30     {
31         per[x]=y;
32         if(rank[x]==rank[y])
33             rank[y]+=1;
34     }     
35 }
36 
37 bool same(int x,int y)
38 {
39     return find(x)==find(y);
40 }

 

并查集详解请访问：（通俗易懂解释）

---

接下来来看几个例子：

hdu 1213 how many tables

题目大意：有一个人过生日，请到了他的诸多朋友，但是这些朋友之间有的认识，有的不认识。这个人想尽可能的把相互之间认识的人凑到一张桌子上，不认识的人则去另一张桌子。朋友们互相认识的规则是：比如a认识b，b认识c，那么a，b，c就可以凑到一桌子上。现在问：他的朋友们以这样的规则能凑够几桌。

解题思路：运用并查集，把相互认识的人都联合一下，到最后计算数组中有几个per值等于自身的人就可以了。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int f[1005];
 6 
 7 void init(int n)
 8 {
 9     for(int i=1;i<=n;i++)
10         f[i]=i;
11 }
12 
13 int find(int a)
14 {
15     while(a!=f[a])
16     {
17         a=f[a];
18     }
19     return a;
20 }
21 
22 void combin(int a,int b)
23 {
24     int ta,tb;
25     ta=find(a);
26     tb=find(b);
27     
28     if(ta!=tb)
29         f[ta]=tb;
30 }
31 
32 int answer(int n)
33 {
34     int sum=0;
35     for(int i=1;i<=n;i++)
36         if(f[i]==i)
37             sum++;
38         return sum;
39 }
40 
41 int main()
42 {
43     
44     int t;
45     cin >> t;
46     while(t--)
47     {
48         int n,m;
49         cin >> n >> m;
50         init(n);
51         int a,b;
52         for(int i=0;i<m;i++)
53             cin >> a >> b,combin(a,b);
54         cout << answer(n) << endl ;
55     }
56     
57     return 0;
58 }

---

hdu 1232 畅通工程

此处略去题目大意……

解题思路：其实这个题目和上一个题异曲同工，就是变换了一下条件，我们假设村子是上题的朋友，那么路就是朋友们之间的关系，那么两堆朋友之间连线，其实只需要一次就可以了，同样，三堆朋友之间要想相互认识，只需要两个关系就可以了，所以我们很容易可以得出朋友们要想都认识，只需要把朋友堆数 - 1 就可以了。

代码只需要将上题的输出结果-1即可 ，不再贴出。

---

poj 2236 wireless network

题目大意：一片废弃的地方，acm协会正在进行救援，可是所有电脑的通信设施都被破坏了，被修复好的电脑的信号传输距离只有d米，现在给出所有电脑的坐标，然后给出指令s与o，s后跟两个数字代表两个电脑的编号，询问这两台电脑是否能通信，如果能则输出success，否则输出fall；o后跟一个编号，代表修好一定电脑。

解题思路：此题运用并查集，在修复好一台电脑之后遍历所有修好的电脑，如果两点间距离小于d米，则连通两个点；遇到s的时候只需要判断是否连通即可。

  1 #include<iostream>
  2 #include<cmath>
  3 using namespace std;
  4 #define maxn 1005
  5 
  6 //坐标 
  7 struct pos{
  8     int x,y;
  9     int par_id;        //父辈id 
 10     int rank;            //树的高度 
 11 }; 
 12 
 13 struct pos par[maxn];        //记录父亲 
 14 bool isok[maxn];    //是否被修复成功 
 15 
 16 float distance(struct pos a,struct pos b)
 17 {
 18     float dis=sqrt(fabs(a.x-b.x)*fabs(a.x-b.x)+fabs(a.y-b.y)*fabs(a.y-b.y));
 19     return dis;
 20 }
 21 
 22 void init(int n)
 23 {
 24     for(int i=1;i<=n;i++)
 25     {
 26         par[i].par_id=i;
 27         par[i].rank=0;
 28         isok[i]=false;    
 29     }
 30 }
 31 
 32 //查树根 
 33 int find(int x)
 34 {
 35     if(par[x].par_id==x)
 36         return x;
 37     else
 38         return par[x].par_id=find(par[x].par_id);
 39 }
 40 
 41 //合并 
 42 void unite(int x,int y)
 43 {
 44     x=find(x);
 45     y=find(y);
 46     if(x==y)
 47         return;
 48     if(par[x].rank<par[y].rank)
 49         par[x].par_id=y;
 50     else{
 51         par[y].par_id=x;
 52         if(par[x].rank==par[y].rank)
 53             par[x].rank++;
 54     }
 55 }
 56 
 57 //判断x和y是不是同一个集合
 58 bool same(int x,int y)
 59 {
 60     return find(x)==find(y);
 61 } 
 62 
 63 int main()
 64 {
 65     int n,d;
 66     char c;
 67     cin >> n >> d;
 68     init(n);
 69     for(int i=1;i<=n;i++)
 70     {
 71         int x,y;
 72         cin >> x >> y; 
 73         par[i].x=x;
 74         par[i].y=y;
 75     }
 76     
 77     while(cin >> c)
 78     {
 79         int p,q;
 80         if(c=='o')
 81         {
 82             cin >> p;
 83             isok[p]=true;
 84             for(int i=1;i<=n;i++)
 85             {
 86                 if(isok[i]==true&&i!=p)
 87                 {
 88                     struct pos a,b;
 89                     a.x=par[i].x;
 90                     a.y=par[i].y;
 91                     a.par_id=par[i].par_id;
 92                     b.x=par[p].x;
 93                     b.y=par[p].y;
 94                     b.par_id=par[p].par_id;
 95                     if(distance(a,b)<=d)
 96                     {
 97                     //    cout << distance(a,b) << endl;
 98                         unite(p,i);
 99                     }
100                         
101                 }
102             }
103         }
104         else if(c=='s')
105         {
106             cin >> p >> q;
107             if(same(p,q))
108                 cout << "success\n";
109             else
110                 cout << "fail\n";
111         }
112 //        for(int i=1;i<=n;i++)
113 //            cout << par[i].par_id << " ";
114 //        cout << endl;
115     }
116     return 0;
117 }

---

poj 1703 find them, catch them

题目大意：有两个帮派，警察现在抓住了n个罪犯，输入字母a或d，后面跟着两个罪犯的编号。如果字符是a，则代表这一次询问：如果不是一个帮派，则输出“in different gangs.”；是一个帮派输出"in the same gang."；否则输出“not sure yet.”。如果是字符d，那就代表着后面的两个编号不属于一个帮派！

解题思路：需要一个标记数组vis，用来标记两个罪犯(a,b)不属于同一个帮派，如果标记数组两个罪犯都为0则代表不确定是哪个帮派，并且让vis[a]=b,vis[b]=a；如果vis[a]==0&&vis[b]!=0，则让vis[b]=a，并且连通a,vis[b]；如果vis[b]==0&&vis[a]!=0，则让vis[a]=b，并且连通b,vis[a]；最后一种情况是a与b的标记数组都不为0，那么连2019-07-21通a,vis[b]，连通b,vis[a]最后判断即可。

  1 //#include<iostream>
  2 //using namespace std;
  3 #include<stdio.h>
  4 #define maxn 100010
  5 
  6 int per[maxn],rank[maxn],vis[maxn];
  7 
  8 void init(int n)
  9 {
 10     int i;
 11     for(i=1;i<=n;i++)
 12     {
 13         per[i]=i;rank[i]=0;vis[i]=0;
 14     }
 15         
 16 }
 17 
 18 int find(int x)
 19 {
 20     if(x==per[x])
 21         return x;
 22     return per[x]=find(per[x]);
 23 }
 24 
 25 void unite(int x,int y)
 26 {
 27     x=find(x);
 28     y=find(y);
 29     if(x==y)
 30         return;
 31     if(rank[x]>rank[y])
 32         per[y]=x;
 33     else
 34     {
 35         per[x]=y;
 36         if(rank[x]==rank[y])
 37             rank[y]+=1;
 38     }     
 39 }
 40 
 41 int same(int x,int y)
 42 {
 43     if(find(x)==find(y))
 44         return 1;
 45     
 46 }
 47 
 48 int main()
 49 {
 50 //    ios::sync_with_stdio(false);
 51     int t;
 52     scanf("%d",&t);
 53 //    cin >> t;
 54     while(t--)
 55     {
 56         int n,m;
 57         scanf("%d%d",&n,&m);
 58 //        cin >> n >> m;
 59         init(n);
 60         while(m--)
 61         {
 62             int a,b;
 63             char c[2];
 64             scanf("%s",c);
 65             //getchar();
 66             scanf("%d%d",&a,&b);
 67             //cin >> c >> a >> b;
 68             //联立 
 69             //printf("%c\n",c);
 70             if(c[0]=='d')
 71             {
 72                 if(vis[a]==0&&vis[b]==0)
 73                 {
 74                     vis[a]=b;
 75                     vis[b]=a;
 76                 }
 77                 else if(vis[a]==0)
 78                 {
 79                     vis[a]=b;
 80                     unite(a,vis[b]);
 81                 }
 82                 else if(vis[b]==0)
 83                 {
 84                     vis[b]=a;
 85                     unite(b,vis[a]);
 86                 }
 87                 else{
 88                     unite(a,vis[b]);
 89                     unite(b,vis[a]);
 90                 }
 91             }
 92             else{
 93                 if(same(a,b))
 94                     printf("in the same gang.\n");
 95                     //cout << "in the same gang.\n";
 96                 else if(same(a,vis[b]))
 97                     //cout << "in different gangs.\n";
 98                     printf("in different gangs.\n");
 99                 else
100                     printf("not sure yet.\n");
101                     //cout << "not sure yet.\n";
102             }
103         }
104     }
105     
106     return 0;
107 }