并查集学习笔记

顾名思义，并查集有两个最主要的作用：合并集合和查询某两个元素是不是在同一个集合内。或者说：

(资料图)

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。 ——百度百科

如果两个元素在一个集合里，那么我们可以把这一个集合理解为一个家族，一个元素是另外元素的父亲，如果集合中出现更多元素，那么这个家族会更加庞大，但无论如何，都会有一个最远公共祖先（我瞎命名的，方便描述），由于集合本身具有无序性，所以说这个最大的祖先可以是集合中的任何一个元素，所有以这个元素为祖宗的数就是集合中的数，现在假设在集合 \(A\) 中有这样的祖先 \(a\) ，如果想要将集合 \(A\) 与集合 \(B\) 合并，那么设集合 \(B\) 中的最远公共祖先为 \(b\) ，如果将 \(a\) 的祖先改成 \(b\) ，那么集合 \(A\) 、 \(B\) 中所有的元素都有一个共同的祖先，所以此时他们就被合并为同一个集合了。这样子的话，如果想要查找 \(a\) 和 \(b\) 是否在一个集合中，只需要看他们的祖先是否相同了

有没有发现这样的思路与树很像？所以说并查集也是一种树形的数据结构，合并就是将森林变成树，而查询则是查询两个子节点是否在同一棵树上

模版题：洛谷P3367首先是一个必不可少的数组： \(fa_i\) 即一个元素的父亲（稍后会有优化），一开始，每个元素自己为一个集合，所以说初始化，令元素的父亲为自己：

for(int i=1;i<=n;i++){fa[i]=i;}

接下来，如何寻找祖宗呢？这里采用递归的方式，如果一个元素的父亲是它本身的话，那么他就是这个集合中的最远公共祖先，所以可以写出 \(find()\) ：

int find(int x){if(fa[x]==x) return x;return find(fa[x]);}

合并集合也就是让一个集合的祖宗的父亲为另一个集合的祖宗：

fa[find(y)]=find(z);

查询操作：

if(find(y)==find(z))

完整代码：

#includeint fa[10005];int find(int x){if(fa[x]==x) return x;return find(fa[x]);}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(x==1){fa[find(y)]=find(z);}else{if(find(y)==find(z)){printf("Y\n");}else{printf("N\n");}}} return 0;} 

这时候我们会发现一个很尴尬的问题——超时了。

考虑 \(fa_i\) 可以直接保存它的祖先而非父亲，这样递归函数可以省去很多时间，也就是说，我们可以将原来的树转化为一个除了根节点就是叶子的树，于是修改 \(find()\) ：

int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);}

得到 \(ACcode\) ：

#includeint fa[10005];int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(x==1){fa[find(y)]=find(z);}else{if(find(y)==find(z)){printf("Y\n");}else{printf("N\n");}}} return 0;} 

洛谷P1536这题太过于板了，不给过程了。

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 ——百度百科

或者说，在有 \(n\) 个节点的有 \(k\) 条边的图里保留 \(n-1\) 条边，使边的长度总和最小

一种用来实现最小生成树的算法其原理类似贪心，从小到大地顺次排列 \(k\) 条边，在不出现自环的情况下顺次加入边，直至加入 \(n-1\) 条边

并查集起到的作用是：查自环如果两个点已经属于一个集合（联通）时，那么再出现一条链接两点的边，必定形成自环。

#include#includeusing namespace std;int n,m;int fa[5005];int ans,cnt;struct e{int x,y,c;}edge[200005];bool cmp(e a,e b){return a.c

#include#includeusing namespace std;int n,m;int fa[2005];int find(int x){if(fa[x]==x) return fa[x];else return fa[x]=find(fa[x]);}int ans;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=2*n;i++){fa[i]=i;}for(int i=1;i<=m;i++){char a;int b,c;cin>>a;scanf("%d%d",&b,&c);if(a=="E"){fa[find(b+n)]=find(c);fa[find(c+n)]=find(b);}if(a=="F"){fa[find(b)]=fa[find(c)];}}for(int i=1;i<=n;i++){if(fa[i]==i)ans++;}printf("%d",ans);return 0;}