学习笔记：并查集

并查集：即支持对集合进行合并和查询的一种数据结构。

合并：将元素a和元素b所在的集合合并成一个集合。

查询：询问a和b是否在同一个集合。

问题引入： 一个县城有若⼲干个村庄，标记为$1,2,3,4......n$，刚开始这$n$个村庄彼此都是不相通的，也就是说每个村庄都是独立的，现在有若干次操作，每次操作给两个数$x$和$y$，表示$x$和$y$之间连通了一条路。经过这若干次操作后问$a$村庄能否到$b$村庄。

假设我们有一个$int$型数组$par$[ ]，我们用这个数组中的元素$par$[ $i$ ]来表示第$i$个村庄和$par$[ $i$ ]之间存在一条通路。

很显然$par$[ i ]的初始值就是$i$，表示第$i$个村庄和其他任何一个村庄没有通路，下面用一段程序来初始化$par$[ ]数组。

void init(){ for(int i=1;i<=n;i++) par[i]=i; }

接下来，就到了若干次操作的环节了，我们假设有六个村庄编号$1$~$6$。 $\bullet$第一次操作：$x=1$ , $y=2$，更新数组$par[2]=1$，表示$2$结点的父亲结点是$1$。

$i$123456$par[i]$113456

$\bullet$第二次操作：$x=4$ , $y=6$，更新数组$par[6]=4$，表示$6$结点的父亲结点是$4$。

$i$123456$par[i]$113454

$\bullet$第三次操作：$x=3$ , $y=6$，按常理来说我们应该更新数组$par[6]=3$，但是问题来了，如果这样做了之后$4$和$6$之间的路被抹除了，这说明第4个村庄就会出现 其他村庄没有和它有通路的情况，但是实际上$3,4,6$这三个村庄是连通的，如图： 我们何不找到表示$6$结点的父亲结点$3$，然后将$4$结点表示为$3$的父亲结点呢。这样就不会出现上述问题了。实际上如果结点$a$和结点$b$的根不一样，将结点$a$和结点$b$合并就是将其根合并。那么数组就更新了：

$i$123456$par[i]$113354

上述合并结点的过程代码如下：

void join(int x,int y) { int fx=Find(x);//Find(x)函数就是查找x的根 int fy=Find(y); if(fx!=fy){ par[fy]=fx; } }

$\bullet$查询：那么一系列操作完了之后就要开始查询了，假如查询$3$和$6$，那我们就先看看$par[6]=4$，我们就再顺藤摸瓜找$par[4]=3$，再顺藤摸瓜找$par[3]=3$发现$3$就是根结点，并且刚好找到了$3$就不用继续找下去了，说明$3$和$6$之间存在通路。问题又来了，如果数据足够大，那么这个过程就太浪费时间了果断舍弃。我们就需要将路径压缩，即可以用递归实现代码如下：

int Find(int x) { if(par[x]==x)return x; else { par[x]=Find(par[x]); return par[x]; } }

经过$Find(6)$函数后：$6$的根结点也是$3$了 可见路径压缩可以降低时间复杂度。 最后：查询$a$和$b$之间是否存在通路就只需看$Find(a)$和$Find(b)$是否相等就ok了 最最后再来个题感受一下：

Problem Description

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最少还需要建设的道路数目。

Sample Input

4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0

Sample Output

1 0 2 998

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<math.h> using namespace std; const int maxn=1e3+10; int par[maxn]; int vis[maxn]; int n,m; void init(){ for(int i=1;i<=n;i++) par[i]=i,vis[i]=0; } int Find(int x) { if(par[x]==x)return x; else { par[x]=Find(par[x]); return par[x]; } } void join(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy){ par[fy]=fx; } } void check() { int ans=0; for(int i=1;i<=n;i++){ vis[Find(par[i])]=1;//把各个根节点对应到vis数组里并标记 } for(int i=1;i<=n;i++){ if(vis[i])ans++;//找有多少个独立的根节点，即有多少个集合 } cout<<ans-1<<endl; } int main() { while(scanf("%d%d",&n,&m)&&n) { init(); while(m--){ int x,y; scanf("%d%d",&x,&y); join(x,y); } check(); } return 0; }