介绍
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的 合并及查询 问题。
其主要操作为：
Union(合并) ：将两个节点所在集合合并为一个集合
Find (查询) :查询某个节点属于哪个集合(即返回所在树的根节点)
图示：
通过上面的表述，恐怕我们并不清楚并查集到底是什么样子的？
下面我们用 图来表示一下
有四个节点我们编号为1，2，3，4，也可以有四棵树，每棵树只有一个节点，该节点即为根节点。这四棵树组成的集合（森林 就是我们所说的并查集
我们使用数组存储 ，上方所示即为
每个节点即为一个集合，每个集合的根节点为自己
合并: 所谓合并就是两棵树合并为一棵树，就是把上面两个节点联系在一起；比如我们合并1，2 两个节点，并且让2 为根节点(也可以1为根节点，这里以2为根节点示例)
经过合并之后，只有三个集合即三棵树 ，存储的数组变化为
编号为1节点和编号为2的节点 为一个集合，且以2为根，故1号位置存储编号2
查询： 找到系欸但所在集合的根节点
以查询编号为1的节点为例：
我们在数组中找1号位置值为2 ，与编号不同
查找2号位置，值为2，与编号相同，所以编号为1的节点的根节点为2
代码实现
经过了上面的演示，相信大家对于并查集有了最基本的认识，下面我们进行代码实现。
并查集的基本实现
constint N ;//并查集中的节点个数int p[N];//存放节点所在树的根节点voidinit(){//初始化，刚开始每个节点都是一棵树，根节点就是它自己for(int i=1;i<=N;i++){
p[i]=i;}}intFind(int x){if(p[x]!=x){//如果不相等，则根节点并非x , 那么去找p[x]的父节点returnfind(p[x]);}return p[x];}voidUnion(int x,int y){// 找到x，y所在树的根节点int px=find(x),py=find(y);//根节点不相同，则不是一棵树，进行合并if(px!=py){//合并后的根节点为py
p[px]=py;}}
代码优化
路径压缩
在并查集的操作当中，我们最常使用的是 Find 查询操作 。查询操作的复杂度决定了整体运行效率。
那么思考一下什么情况下，查询操作效率会很低呢？
思考一下树的高度很大的时候。
倘若我们查询4号节点，需要从4号节点往上进行查询，复杂度即为O（h），h为树的高度 ，倘若对于深处节点查询频繁的话，效率会很低。
因此，为了避免这种情况，出现了路径压缩的方式，其思想是将上面图片的树，改造为如下所示:
每个子节点的父节点即为根节点，查询操作复杂度O（1）即可
优化代码：
intFind(int x){if(p[x]!=x){//如果不相等，则向上查找；find函数返回的结果一定为根节点// 查询结果赋值给p[x]，设置当前节点x的父节点为根节点
p[x]=find(p[x]);}return p[x];}
按秩合并
关于 秩 其实有两种解释 ：一种是树的高度，另一种是树的节点个数（集合大小）我们这里采用的是 树 的高度。
按秩合并其实是一种启发式合并 即：把小的数据结构 合并到大的数据结构当中，并且只增加小的数据结构的 查询 代价 。
情况如图所示: 两个集合进行合并
我们可以观察到最右边的图，合并后，进行查询，效率会更好，这种合并方式就是我们正在讨论的 按秩合并 。
优化代码
constint N ;//并查集中的节点个数int p[N];//存放节点所在树的根节点int rank[N];//存放秩的数组，每个集合的秩进存放在根节点voidinit(){//初始化，刚开始每个节点都是一棵树，根节点就是它自己//每个节点的秩为1for(int i=1;i<=N;i++){
p[i]=i;
rank[i]=1;}}intFind(int x){if(p[x]!=x){//路径压缩 优化
p[x]=find(p[x]);}return p[x];}voidUnion(int x,int y){// 找到x，y所在树的根节点int px=find(x),py=find(y);//根节点不相同，则不是一棵树，进行合并if(px!=py){// 按秩合并 优化if(rank[px]<=rank[py]){
p[px]=py;//两个集合的秩相同，合并后的集合在原基础上加1//原因如下图所示
rank[py]+=(rank[x]==rank[y]?1:0);}else{
p[py]=px;}}}
题目练习：
1250. 格子游戏
链接: https://www.acwing.com/problem/content/1252/
Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。
接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序，帮助他们计算他们是否结束了游戏？
输入格式
输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。
以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R 就是向右连一条边。输入数据不会有重复的边且保证正确。
输出格式
输出一行：在第几步的时候结束。
假如 m 步之后也没有结束，则输出一行“draw”。
数据范围
1≤n≤200 ，
1≤m≤24000
输入样例：
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
输出样例：
4
思路：
输入样例当中给了我们一个点，及其所画的方向 。其实根据这些信息，我们可以得到两个点的信息，那怎么判断是否形成封闭的圆呢？
如图所示，我们只需要画一条线，线的两端为(2,1) (2,2) 即可以形成封闭的圆 。这种情况我们使用并查集是最为简单的，判断两个点是否在同一集合内，在的话可以形成封闭的圆。
代码：
#include<iostream>#include<cstring>usingnamespace std;constint N=40000+10;int p[N];// 将二维坐标转换为唯一的数字表示intget(int x,int y,int n){
x--,y--;return x*n+y;}intfind(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}intmain(){int n=0,m=0;
cin>>n>>m;//初始化for(int i=0;i<n*n;i++){
p[i]=i;}for(int i=1;i<=m;i++){int x=0,y=0;char ch;
cin>>x>>y>>ch;int a=get(x,y,n),b=0;if(ch=='D'){
b=get(x+1,y,n);}elseif(ch=='R'){
b=get(x,y+1,n);}int pa=find(a),pb=find(b);if(pa==pb){//如果在同意集合内，形成了封闭的圆，直接返回结果printf("%d\n",i);return0;}
p[pa]=pb;}printf("draw\n");return0;}
1252. 搭配购买
链接：https://www.acwing.com/problem/content/1254/
Joe觉得云朵很美，决定去山上的商店买一些云朵。
商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。
但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
输入格式
第 1 行包含三个整数 n，m，w，表示有 n 朵云，m 个搭配，Joe有 w 的钱。
第 2∼n+1行，每行两个整数 ci，di 表示 i 朵云的价钱和价值。
第 n+2∼n+1+m 行，每行两个整数 ui，vi，表示买 ui 就必须买 vi，同理，如果买 vi 就必须买 ui。
输出格式
一行，表示可以获得的最大价值。
数据范围
1≤n≤10000,
0≤m≤5000,
1≤w≤10000,
1≤ci≤5000,
1≤di≤100,
1≤ui,vi≤n
输入样例：
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
输出样例：
1
思路:
题目中给我们提供了一些物品的价格和价值；要求买u必须要买v，买v也必须买u ； 倘若买v还必须买w ，则u，v，w 可以认为是一个整体，要买一起买，不买则全部不买；如果把所有关联的物品全部看作一个整体，对于每个整体而言，只有买或者不买两种选择，求一定价钱内能买到物品的最大价值 即可转换为经典的01背包问题 。
而那些物品可以看作一个整体，则可使用并查集进行求取，根节点存储整个集合的价格和价值。
代码:
#include<iostream>#include<cstring>usingnamespace std;constint N=10000+10;int p[N];int cost[N],value[N];intfind(int x){if(p[x]!=x){
p[x]=find(p[x]);}return p[x];}intmain(){int n=0,m=0,w=0;scanf("%d%d%d",&n,&m,&w);for(int i=0;i<n;i++){
p[i]=i;}for(int i=0;i<n;i++){int c=0,d=0;scanf("%d%d",&c,&d);
cost[i]=c,value[i]=d;}for(int i=0;i<m;i++){int u=0,v=0;scanf("%d%d",&u,&v);
u--,v--;int pu=find(u),pv=find(v);if(pu!=pv){
p[pu]=pv;//根节点加上新加入节点对应的价格和价值
cost[pv]+=cost[pu];
value[pv]+=value[pu];}}int dp[N];memset(dp,0,sizeof dp);for(int i=0;i<n;i++){if(p[i]==i){for(int j=w;j>=cost[i];j--){
dp[j]=max(dp[j],dp[j-cost[i]]+value[i]);}}}
cout<<dp[w]<<endl;return0;}
237. 程序自动分析
链接：https://www.acwing.com/problem/content/239/
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。
例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
输入格式
输入文件的第 1 行包含 1 个正整数 t，表示需要判定的问题个数，注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第 1 行包含 1 个正整数 n，表示该问题中需要被满足的约束条件个数。
接下来 n 行，每行包括 3 个整数 i,j,e，描述 1 个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1，则该约束条件为 xi=xj；若 e=0，则该约束条件为 xi≠xj。
输出格式
输出文件包括 t 行。
输出文件的第 k 行输出一个字符串 YES 或者 NO，YES 表示输入中的第 k 个问题判定为可以被满足，NO 表示不可被满足。
数据范围
1≤n≤10^5
1≤i,j≤10^9
输入样例：
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例：
NO
YES
思路:
在这个题目当中，可以把输入分为两类，一类是相等的条件，另一类是不等的条件；倘若我们把相等的条件放在一遍，去看不等的条件，倘若不等的条件种两个变量出现在相等条件中，一定不被满足；倘若查询完毕后，没有出现刚才不满足情况，则一定是满足的。
把相等条件的变量全部放入并查集，查询不等的条件，倘若对应的两个变量在一个集合内部，则必不满足；不出现刚才必不满足的情况，则一定满足。
注: 数据量最大为 10^9 以此 来申请并查集的空间，则会超过题目给予的64MB大小；反观条件次数n为 10^6，则变量最多只有2 * 10^6 ,我们可以离散化处理，将大范围的变量处理到小范围上。
代码:
#include<iostream>#include<cstring>#include<vector>#include<unordered_map>usingnamespace std;/*
注：数据量过大，需要进行离散化，将数据放在较小的定义域内
*/constint N=2000010;int p[N];
unordered_map<int,int> map;intfind(int x){if(p[x]!=x){
p[x]=find(p[x]);}return p[x];}//离散化处理函数intget(int x){staticint t=1;if(map.count(x)==0){
map[x]=t++;}return map[x];}intmain(){int t=0;scanf("%d",&t);while(t--){for(int k=1;k<N;k++){
p[k]=k;}int n=0;scanf("%d",&n);
vector<pair<int,int>> vec1;
vector<pair<int,int>> vec2;for(int k=0;k<n;k++){int i=0,j=0,e=0;scanf("%d%d%d",&i,&j,&e);if(e==0){
vec1.push_back({get(i),get(j)});}elseif(e==1){
vec2.push_back({get(i),get(j)});}}//处理相等的条件for(int k=0;k<vec2.size();k++){int i=vec2[k].first,j=vec2[k].second;int pi=find(i),pj=find(j);if(pi!=pj){
p[pi]=pj;}}//遍历不等的条件，继续判断int flag=true;for(int k=0;k<vec1.size();k++){int i=vec1[k].first,j=vec1[k].second;int pi=find(i),pj=find(j);if(pi==pj){
flag=false;break;}}if(flag){puts("YES");}else{puts("NO");}}return0;}
238. 银河英雄传说
链接: https://www.acwing.com/problem/content/240/
有一个划分为 N 列的星际战场，各列依次编号为 1,2,…,N。
有 N 艘战舰，也依次编号为 1,2,…,N，其中第 i 号战舰处于第 i 列。
有 T 条指令，每条指令格式为以下两种之一：
M i j，表示让第 i 号战舰所在列的全部战舰保持原有顺序，接在第 j 号战舰所在列的尾部。
C i j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数 T，表示共有 T 条指令。
接下来 T 行，每行一个指令，指令有两种形式：M i j 或 C i j。
其中 M 和 C 为大写字母表示指令类型，i 和 j 为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 i 号战舰与第 j 号战舰之间布置的战舰数目，如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 −1。
数据范围
N≤30000,T≤500000
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例：
-1
1
思路:
对于判断是否是同一列，我们可以使用并查集，通过判断是否属于同一个结合来进行判断。
如果属于同一列(即同一集合)，还需要输出之间的距离是多少，这个需要怎么处理呢?
倘若我们有一个数组d[ ] 记录并查集中每个节点到它所属集合的根节点的距离。根节点，我们设置为每列的第一个战舰。
则 对于两艘战舰x,y (x在y前面)而言，他们的距离为 d[y]-d[x]-1 则可以直接得到结果。
因此，我们只需要维护一个数组d[ ] ;
而维护d[ ] 主要在集合合并的时候，进行更新，那怎么更新呢？
对于py集合而言，每个节点到根节点的距离只需要加上 3 的长度即可
而3的长度 ，如图所示为2 + 1的结果，线段2的长度为1 ，而线段1的长度为整个px集合节点个数
因此，还需要维护一个数组 Size [ ] 存放每个集合的节点数目
代码实现:
#include<iostream>#include<cstring>usingnamespace std;constint N=30000+10;int p[N];// Size 为该集合的元素个数 dist，该节点到父结点的距离int Size[N],dist[N];intfind(int x){if(p[x]!=x){int root=find(p[x]);//dist[x] 保存的是该节点到父节点的距离//dist[p[x]] 保存的是 x父节点到根节点的距离 (由上面的递归得到的)
dist[x]+=dist[p[x]];
p[x]=root;}return p[x];}intmain(){for(int i=1;i<N;i++){
p[i]=i;
Size[i]=1;
dist[i]=0;}int t=0;
cin>>t;while(t--){char op;int i=0,j=0;
cin>>op>>i>>j;if(op=='M'){int pi=find(i),pj=find(j);if(pi!=pj){
p[pi]=pj;//将pi集合放到pj集合中
dist[pi]=Size[pj];
Size[pj]+=Size[pi];//更新pj集合 元素个数}}elseif(op=='C'){int pi=find(i),pj=find(j);if(pi==pj){//若i==j 则 距离为0 否则 abs()printf("%d\n",max(0,abs(dist[i]-dist[j])-1));}else{printf("-1\n");}}}return0;}
239. 奇偶游戏
链接: https://www.acwing.com/problem/content/description/241/
小 A 和小 B 在玩一个游戏。
首先，小 A 写了一个由 0 和 1 组成的序列 S，长度为 N。
然后，小 B 向小 A 提出了 M 个问题。
在每个问题中，小 B 指定两个数 l 和 r，小 A 回答 S[l∼r] 中有奇数个 1 还是偶数个 1。
机智的小 B 发现小 A 有可能在撒谎。
例如，小 A 曾经回答过 S[1∼3] 中有奇数个 1，S[4∼6] 中有偶数个 1，现在又回答 S[1∼6] 中有偶数个 1，显然这是自相矛盾的。
请你帮助小 B 检查这 M 个答案，并指出在至少多少个回答之后可以确定小 A 一定在撒谎。
即求出一个最小的 k，使得 01 序列 S 满足第 1∼k 个回答，但不满足第 1∼k+1 个回答。
输入格式
第一行包含一个整数 N，表示 01 序列长度。
第二行包含一个整数 M，表示问题数量。
接下来 M 行，每行包含一组问答：两个整数 l 和 r，以及回答 even 或 odd，用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。
输出格式
输出一个整数 k，表示 01 序列满足第 1∼k 个回答，但不满足第 1∼k+1 个回答，如果 01 序列满足所有回答，则输出问题总数量。
数据范围
N≤10^9,M≤5000
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3
思路1：
我们观察数据范围，发现为10^9的空间，过于庞大，所以会使用离散化的技巧 来进行优化。
我们思考题目，发现S其实一个前缀和数组，S[i]表示 i位置及其前面所含的1的个数 ; [l,r]范围的1的个数 即为S[ r ]- S [ l-1 ]
[ l,r ] 如果有奇数个1 ，则 S[ r ]和S[ l-1 ] 奇偶性必不相同，两者一个为奇数，另一个必定为偶数
倘若[l,r]范围内有偶数个1，则则 S[ r ]和S[ l-1 ] 奇偶性相同，一个为奇数，另一个必定为奇数 或者一个为偶数，另一个必定为偶数
通过上面的描述，我们发现，输入的回答，可以使用条件集合进行表示
对于x位置而言 x数字表示S[x]为偶数 x+Base 数字表示S[x]位置为奇数
注：Base其实是一个不妨碍的整数
集合当中存放必然成立的条件
我们可以通过代码来回顾一下这个方案
代码实现:
#include<iostream>#include<string>#include<unordered_map>usingnamespace std;constint N=5000*4+10;// 将Base设置为[x,y] 和[x+Base,y+Base] 区间互不影响的数值即可int Base=N/2;int p[N];//进行离散化处理
unordered_map<int,int> map;intget(int x){staticint t=0;if(map.count(x)==0){
map[x]=++t;}return map[x];}//并查集 find 函数intfind(int x){if(p[x]!=x){
p[x]=find(p[x]);}return p[x];}intmain(){//初始化并查集for(int i=0;i<N;i++){
p[i]=i;}int n=0,m=0;scanf("%d%d",&n,&m);int result=m;for(int i=1;i<=m;i++){int l=0,r=0;
string type;
cin>>l>>r>>type;int x=get(l-1),y=get(r);if(type=="even"){//区间内有偶数个1 则 S[x] 和S[y] 奇偶性相同，//如果不同，必不合法if(find(x+Base)==find(y)||find(x)==find(y+Base)){
result=i-1;break;}//S[x] 和S[y] 奇偶性相同， //则 S[x]为奇数则S[y] 必为奇数 x+Base表示S[x]为奇数// S[x]为偶数则S[y] 必偶数
p[find(x)]=find(y);
p[find(x+Base)]=find(y+Base);}else{//区间内有奇数个1 则 S[x] 和S[y] 奇偶性不同，//如果相同，必不合法if(find(x)==find(y)||find(x+Base)==find(y+Base)){
result=i-1;break;}//S[x] 和S[y] 奇偶性不同， //则 S[x]为奇数则S[y] 必为偶数 // S[x]为偶数则S[y] 必为奇数
p[find(x+Base)]=find(y);
p[find(x)]=find(y+Base);}}printf("%d\n",result);return0;}
思路2：
带边权的并查集：
我们观察数据范围，发现为10^9的空间，过于庞大，所以会使用离散化的技巧 来进行优化。
我们思考题目，发现S其实一个前缀和数组，S[i]表示 i位置及其前面所含的1的个数 ; [l,r]范围的1的个数 即为S[ r ]- S [ l-1 ]
[ l,r ] 如果有奇数个1 ，则 S[ r ]和S[ l-1 ] 奇偶性必不相同，两者一个为奇数，另一个必定为偶数
倘若[l,r]范围内有偶数个1，则则 S[ r ]和S[ l-1 ] 奇偶性相同，一个为奇数，另一个必定为奇数 或者一个为偶数，另一个必定为偶数
d[x] 表示 x 与根节点 的 奇偶性关系，0表示奇偶性相同，1表示奇偶性不同
[x,y]区间若有奇数个1，则S[x-1] 与S[y ]奇偶性不同
若 px=py 则d[x] ^ d [y] ==1 则无矛盾 ；d[ x ] ^d[ y ] == 0 则有矛盾
[x,y]区间若有偶数个1，则S[x-1] 与S[y ]奇偶性相同
若 px=py 则d[x] ^ d [y] ==0 则无矛盾 ；d[ x ] ^d[ y ] == 1 则有矛盾
问题一：
[x,y]区间若有奇数个1，则S[x-1] 与S[y ]奇偶性不同
若px!=py,则需要合并区间 根节点p[px]=py 而d[ ] 如何更新呢？
问题二：
[x,y]区间若有偶数个1，则S[x-1] 与S[y ]奇偶性相同
若px!=py,则需要合并区间 根节点p[px]=py 而d[ ] 如何更新呢？
对于问题一而言：
我们希望d[x] ^ d[ y ] ^ ? =1
倘若d[ x ]^d[y ] =0 则?=1 而 d[x] ^d[y ] = 1 的话，则 ?=0
因此? =d [ x ] ^d[ y ]^ 1
同理：
对于问题一而言：
我们希望d[x] ^ d[ y ] ^ ? =0
倘若d[ x ]^d[y ] =0 则?=0 而 d[x] ^d[y ] = 1 的话，则 ?=1
因此? =d [ x ] ^d[ y ]
我们可以通过代码来回顾一下这个方案
代码实现:
#include<iostream>#include<cstring>#include<unordered_map>#include<string>usingnamespace std;constint N=5000*2+10;int p[N],d[N];//离散化处理
unordered_map<int,int> map;intget(int x){staticint t=1;if(map.count(x)==0){
map[x]=t++;}return map[x];}intfind(int x){if(p[x]!=x){int root=find(p[x]);
d[x]^=d[p[x]];
p[x]=root;}return p[x];}intmain(){for(int i=1;i<N;i++){
p[i]=i;}int n=0,m=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int l=0,r=0;
string type;
cin>>l>>r>>type;// 我们要判断 l-1和r位置的奇偶性int x=get(l-1),y=get(r);//偶数为0 ，奇数为1int t=0;if(type=="odd"){
t=1;}int px=find(x),py=find(y);if(px!=py){
p[px]=py;
d[px]=d[x]^d[y]^t;}else{if((d[x]^d[y])!= t){printf("%d\n",i-1);return0;}}}printf("%d\n",m);return0;}
代码模板:
按秩合并+路径压缩
constint N ;//并查集中的节点个数int p[N];//存放节点所在树的根节点int rank[N];//存放秩的数组，每个集合的秩进存放在根节点voidinit(){//初始化，刚开始每个节点都是一棵树，根节点就是它自己//每个节点的秩为1for(int i=1;i<=N;i++){
p[i]=i;
rank[i]=1;}}intFind(int x){if(p[x]!=x){//路径压缩 优化
p[x]=find(p[x]);}return p[x];}voidUnion(int x,int y){// 找到x，y所在树的根节点int px=find(x),py=find(y);//根节点不相同，则不是一棵树，进行合并if(px!=py){// 按秩合并 优化if(rank[px]<=rank[py]){
p[px]=py;//两个集合的秩相同，合并后的集合在原基础上加1//原因如下图所示
rank[py]+=(rank[x]==rank[y]?1:0);}else{
p[py]=px;}}}
维护每个集合的大小
constint N ;//并查集中的节点个数int p[N];//存放节点所在树的根节点int size[N];//根节点位置存放集合大小voidinit(){//初始化，刚开始每个节点都是一棵树，根节点就是它自己//每个集合的大小为1for(int i=1;i<=N;i++){
p[i]=i;
size[i]=1;}}intFind(int x){if(p[x]!=x){//路径压缩 优化
p[x]=find(p[x]);}return p[x];}voidUnion(int x,int y){// 找到x，y所在树的根节点int px=find(x),py=find(y);
p[px]=py;
size[py]+=size[px];}
维护到根节点距离
constint N ;//并查集中的节点个数int p[N];//存放节点所在树的根节点int dist[N];//到根节点的距离voidinit(){//初始化，刚开始每个节点都是一棵树，根节点就是它自己for(int i=1;i<=N;i++){
p[i]=i;
dist[i]=0;}}intFind(int x){if(p[x]!=x){//路径压缩 优化int root=find(p[x]);
dist[x]+=dist[p[x]];
p[x]=root;}return p[x];}voidUnion(int x,int y){// 找到x，y所在树的根节点int px=find(x),py=find(y);
p[px]=py;
size[px]? 根据具体情况进行初始化
//合并的时候我们仅更新px到合并后根节点py的距离//原px的其他节点会在find函数中自动更新距离}
版权归原作者 凌星An 所有， 如有侵权，请联系我们删除。