欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-05 20:25:03
不想看模板,想直接看题目的请戳下面目录: 目录: HDU 1213 How Many Tables【传送门】 HDU 1232 畅通工程 【传送门】 POJ 2236 Wireless Network 【传送门】 POJ 1703 Find them, Catch them 【传送门】 先上模板: ......

不想看模板,想直接看题目的请戳下面目录:

目录:

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 }