并查集初步

先来几道基础并查集。

http://ybt.ssoier.cn:8088/problem_show.php?pid=1346
http://ybt.ssoier.cn:8088/problem_show.php?pid=1385

看看上面两道题大致对并查集的作用有了一定的了解，是不是感觉知道求答案的思路，但就是很难用代码实现。

今天就是来介绍c++图论中的重要一环，个人认为并查集在图论中作用巨大！

大致思想：

判定两支队伍是否属于同一个集合，方法就是看他们的最高领袖是否是同一个人。
同样的，判断两个元素是否属于同一个集合，就看他们的最高父节点是否是同一个。
然后是集合的合并，合并其实就非常简单，让其中任何一个集合的最高父节点变成另外一个集合的最高父节点的子节点，合并就完成了。

其中找最高父节点（也就是祖先）是并查集的关键。

这里就使用一个father()函数来实现（既可以用while循环，也可以用递归，看个人喜好）

1 int f[10005];//记录每个点的祖先。
2 int father(int v)
3 {
4     while(f[v]!=v)//判断这个点自身是不是指向自己，
5     {             //如果指向自己，这个点暂时就是这个集合的祖先
6         v=f[v];
7     }
8     return v;
9 }

但光靠上面的father()函数有点浪费时间，因为每个点在循环（或递归）中要跳多次才能找到自己的祖先，于是就出现下面的优化方式，称为路径压缩。

这次我们用递归写。

1 int f[10005]
2 int father(int v)
3 {
4     if(f[v]!=v)f[v]=father(f[v]);
5     return f[v];
6 }

相信可以看出，运用路径压缩就是在寻找祖先的过程中，顺便改变了这个点的长辈结点们所指向的祖先，优化之后跳跃的次数。

如下图所示

最后在注意一下每个结点在最初要将自己的祖先指向自己，因为在最初他们各自都是独立的自己是自己的祖先。

当然我在网上看到了一个额外的部分，就是还添加了一个rank[]数组来存储每个集合的秩。

就是高度（说白了就是有几代人），然后将小的集合加在大的集合上。

但个人觉得这不是必要的，只要指向同个祖先就行了，不过这看个人爱好。

下面来一个模板，既然是模板还是加个rank[]以示完整性。

 1 int father[MAX];   /* father[x]表示x的父节点*/  
 2 int rank[MAX];     /* rank[x]表示x的秩*/  
 3   
 4   
 5  /* 初始化集合*/  
 6 void Make_Set(int x)  
 7 {  
 8     father[x] = x; //根据实际情况指定的父节点可变化  
 9      rank[x] = 0;   //根据实际情况初始化秩也有所变化  
10 }  
11   
12   
13 /* 查找x元素所在的集合,回溯时压缩路径*/  
14 int Find_Set(int x)  
15 {  
16     if (x != father[x])  
17     {  
18         father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华  
19     }  
20     return father[x];  
21 }  
22   
23 /*  
24    按秩合并x,y所在的集合 
25    下面的那个if else结构不是绝对的，具体根据情况变化 
26    但是，宗旨是不变的即，按秩（即树的高度）合并，实时更新秩。 这个树的高度其实可要可不要记不记录都无所谓
27 */  
28 void Union(int x, int y)  
29 {  
30     x = Find_Set(x);  
31     y = Find_Set(y);  
32     if (x == y) return;  
33     if (rank[x] > rank[y])   
34     {  
35         father[y] = x;  
36     }  
37     else  
38     {  
39         if (rank[x] == rank[y])  
40         {  
41             rank[y]++;  
42         }  
43         father[x] = y;  
44     }  
45 }

看完模板之后就来试一下上面的例题吧。

下面是例题2的代码。

 1 #include<cstdio>
 2 using namespace std;
 3 int a[20005];
 4 int b[20005];
 5 int father(int v)
 6 {
 7     int u=v;     
 8     while(a[v]!=v)
 9     {
10         v=a[v];
11     }
12     while(a[u]!=u)
13     {
14         int e=u;
15         u=a[u];
16         a[e]=v;
17     }
18     return v;
19 }
20 int main()
21 {
22     int n,m;
23     scanf("%d%d",&n,&m);
24     for(int i=1;i<=n;i++)
25     {
26         a[i]=i;
27     }
28     for(int i=1;i<=m;i++)
29     {
30         int x,y,p;
31         scanf("%d%d%d",&p,&x,&y);
32         if(p==0)
33         {
34             int a1,b1;
35             a1=father(x);
36             b1=father(y);
37             if(a1!=b1)
38             {
39                 a[a1]=b1;
40             }
41         }
42         else 
43         {
44             if(b[x]==0)b[x]=y;
45             else
46             {
47                 a[y]=father(b[x]);
48             }
49             if(b[y]==0)b[y]=x;
50             else
51             {
52                 a[x]=father(b[y]);
53             }
54         }
55     }
56     int num=0;
57     for(int i=1;i<=n;i++)
58     {
59         if(a[i]==i)num++;
60     }
61     printf("%d",num);
62     return 0;
63 }

如果觉得上面的题都是小菜一碟，那就看看下面的吧。

至少是noip提高+/省选-的。

https://www.luogu.org/problemnew/show/2024食物链

https://www.luogu.org/problemnew/show/1197星球大战

https://www.luogu.org/problemnew/show/1196 银河英雄传说

星球大战解题

这道题看似很长其实也不是十分的难

如果我们去正向摧毁想想都有点困难

要不我们使用逆向思维？

没错这道题就把摧毁转换成修建~~（和平就是好）~~

利用并查集判断联通就好了

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 using namespace std;
 5 vector<int> link[400005];//记录每个点相连接的点。
 6 struct sd{
 7     int x,y;
 8 };//用结构体存每条边。
 9 sd edge[400005];
10 int f[400005];//记录每个点的祖先。
11 int boom[400005];//记录被干掉了的星球
12 int res[400005];
13 int father(int v)
14 {
15     if(f[v]!=v)f[v]=father(f[v]);
16     return f[v];
17 }
18 int main()
19 {
20     int n,m;
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;i++)
23     f[i]=i;
24     for(int i=1;i<=m;i++)
25     {
26         int a,b;
27         scanf("%d%d",&a,&b);
28         link[a].push_back(b);
29         link[b].push_back(a);
30         edge[i].x=a;//存每条边的两个端点。
31         edge[i].y=b;
32     }
33     int k;
34     scanf("%d",&k);
35     for(int i=1;i<=k;i++)
36     {
37         int x1;
38         scanf("%d",&x1);
39         f[x1]=-1;
40         boom[i]=x1;//记录每个爆炸的星球。
41     }
42     int num=0;//用于记录还有多少条边连在一起。
43     for(int i=1;i<=m;i++)
44     {
45         if(f[edge[i].x]!=-1&&f[edge[i].y]!=-1)
46         {
47             int fx=father(edge[i].x);
48             int fy=father(edge[i].y);
49             if(fx!=fy)
50             {
51                 f[fx]=fy;
52                 num++;
53             }
54         }
55     }
56     int sum=n-k-num;//并查集个数==点的个数-边的个数。
57     int kk=1;
58     res[kk]=sum;
59     for(int i=k;i>=1;i--)
60     {
61         f[boom[i]]=boom[i];
62         sum++;//每添加进去一个被摧毁的星球，并查集的个数就要加1。
63         for(int j=link[boom[i]].size()-1;j>=0;j--)
64         {//寻找每个可以与新加的星球向连得星球。
65             int fx;
66             fx=father(boom[i]);
67             if(f[link[boom[i]][j]]!=-1)   
68             {   //注意！！！要判断相连的点是不是被摧毁了，摧毁了则不能相连。
69                 int fy=father(link[boom[i]][j]);
70                 if(fx!=fy)
71                 {
72                     sum--;//每连一对星球，并查集个数减一。
73                     f[fx]=fy;
74                 }
75             }
76         }
77         kk++;
78         res[kk]=sum;//存储每次的并查集个数。
79     }
80     for(int i=kk;i>=1;i--)//倒序输出，记住！！！要倒序。
81     printf("%d
",res[i]);
82     return 0;
83 }