并查集
并查集作用：
1.将两个集合合并
2.询问两个元素是否在一个集合当中
基本原理：
每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个节点都存的是它的父节点，即 p [x] 表示 x 的父节点。
p[x]中储存的是每个节点的父节点，一开始并不是树状的，
而是一个个单独的节点，每个节点都是根节点，都有集合编号，然后通过不断的合并才形成的树状结构
问题一： 如何判断树根
if (p[x]==x)
除根节点以为所有节点都存的是自身的父节点，只有根节点存的是它自己。
问题二： 如何求x的集合编号
没找到就一直访问到它的父节点，直到找到位置。
while (p[x] != x) x = p[x]
优化：路径压缩
只要某一个元素找的根节点
就把这个元素的所有祖宗节点都改成根节点。
int find(int x) { if(p[x]!=x)// x不是自身的父亲，即x不是该集合的代表 return p[x]=find(p[x]); return p[x]; // 查找x的祖先直到找到代表,于是顺手路径压缩 }
问题三：如何合并两个集合
p [find(a)] = p[find(b)];
p[x]=x的集合编号，p[y]是y的集合编号
代码实现
#include<bits/stdc++.h> using namespace std;q const int N = 1e6+10; int p[N]; int find(int x) { if(p[x]!=x)// x不是自身的父亲，即x不是该集合的代表 return p[x]=find(p[x]); return p[x]; // 查找x的祖先直到找到代表,于是顺手路径压缩 } int main() { int n,m; cin>>n>>m; for(int i = 1 ; i <= n ; i ++) p[i]=i; //开始时每个节点都是父节点 while(m--) { string x; cin>>x; int a,b; cin>>a>>b; if(x=="M") p[find(a)]=find(b);//a集合的根节点的父节点变成 b集合的根节点 完成a集合与b集合的合并 else { if(find(a)==find(b)) cout<<"Yes"; else cout<<"No"; puts(""); } } return 0; }
村村通
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 “村村通工程” 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？
输入格式
输入包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 nnn 和道路数目 mmm ；随后的 mmm 行对应 mmm 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 111 到 nnn 编号。
注意：两个城市间可以有多条道路相通。
输出格式
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
输入 #1
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
输出 #1
1 0 2 998
思路：
先初始化，将自己父亲等于自己
**输入两个村庄后就把它们连起来，输入完毕后遍历 从 1 到 n，判断 节点是不是等于他们的父节点 **
所以如果i的父亲为它本身的话 说明 编号为 i 的这条路，与其他路不连通，ans++
但还有一种情况是会有一个节点是所有其他节点的祖先节点，也而且祖先节点也等于他本身、
所以最后需要 ans - 1
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int p[N]; int find(int x) { return (p[x]!=x)?p[x]=find(p[x]):p[x]; } int main() { int n,m; while(cin>>n>>m) { int a,b; int ans=0; for(int i = 1 ; i <= n ; i ++) p[i]=i; while(m--) { cin>>a>>b; a=find(a),b=find(b); p[a]=p[b]; } for(int i = 1 ; i <= n; i ++) { if(find(i)==i) ans++; //如果自己等于自己的父亲 就说明 编号为 i 的这条路，与其他路不连通 } cout<<ans-1<<"\n"; //要减一是因为如果不用修一条路的话 那就会有一个节点是所有其他节点的祖先节点 所以要减去1 } return 0; }
完结散花
ok以上就是对 模拟数据结构之并查集 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
