引言

一个小小的并查集让我们在ccpc卡了那么久(还有unordered_map,如果不是忘了map自动排序这么一回事也不至于试那么多发)，至今仍然心有余恨。所以期末结束的第一件事就是拿下这个可恶的并查集！并狠狠的写一篇博客来纪念它的祭日！（6.27 R.I.P.）废话不多说，下面开始正题：

简单介绍

单看“并查集”这个名字可能没什么概念，它的英文名(Union-Find) 可能还稍微好理解一点。看看官方一点的描述 (豆包生成^_^)：

并查集算法（Union-Find Algorithm），又称不相交集合联合算法（Disjoint Set Union, DSU），是一种用于管理若干不相交集合的高效数据结构，支持以下核心操作：

初始化（Initialize）：将每个元素初始化为独立集合，每个集合的代表元（根节点）为自身。
查找（Find）：确定某个元素所属的集合，返回该集合的代表元（根节点）。
合并（Union）：将两个不同的集合合并为一个集合。

浅浅总结

并查集算法的设计目标是高效处理集合的动态合并与查询问题，其核心思想是通过树形结构表示集合，每个节点存储其父节点信息，根节点作为集合的标识。

算法图解

初始化

可以把整个看作一个大树，最开始它们的根都是它们自己。这一步要进行初始化~

void init(int n)
{parent.resize(n+1);Size.resize(n+1,1);//初始化 刚开始他们的父节点都是自己for(int i=0; i<=n; i++) parent[i]=i;
}

根节点查找

我们进行一些合并的操作，比如下边这个的东西，就是经过一些小的合并操作之后的结果。那么如果此时我们想看某两个元素是否在同一棵树上该怎么搞呢？那么我们只需要看它们的根节点是否相同就行了。比如此时想判断10和3是否属于一棵树，那么分别找它们的根节点并判断就行了。例：10->4->6，3->4->6。代码就像这样：

int find(int x) {while (parent[x] != x) {x = parent[x];  // 逐级向上查找根节点}return x;  // 返回根节点
}

这样的话逻辑上来说好像确实没毛病，但是实际操作之后发现当节点数量足够多的时候，每次查找都要从子节点一点一点朝根节点寻找，效率非常的慢，极其容易超时。仔细再想一下，其实我们不需要树上的其他关系，似乎只需要确定子节点是否属于根节点就行了。那么如果我们直接将树的所有子节点连到根节点上，每次查找的时候就只需要O(1)就可以解决。就像下图：

代码改进：

int find(int x)//寻找根节点
{if(parent[x]!=x)//路径压缩，将路径上的节点直接连接到根节点上parent[x]=find(parent[x]);return parent[x];
}

集合合并

然后再说一下合并的环节。合并的时候不要直接将两个节点连接，这样的话会增加树的高度。合并这个操作对我们的作用就是这俩点所连的所有节点都同属于一棵树，我们直接把它们的根节点连接就行。还有一个问题就是这俩树该哪个连到哪个上边。由于相连之后主动连接的树上所有点的根节点都需要发生变化，所以我们将小树连到大树上，这样的话可以减小工作量。同时统计树大小的Size数组还可以表示此时元素所在树的节点多少。代码：

void unit(int x, int y)//合并集合
{x = find(x);//找根节点y = find(y);if(x==y) return ;//根节点一样就不用连了if(Size[x]<Size[y])//将高度小的树连到高度大的树上{parent[x]=y;Size[y]+=Size[x];}else//合并然后数量相加{parent[y]=x;Size[x]+=Size[y];}
}

连通性检查

然后就是判断操作，用来看是否两个节点可以互通(根节点相同)。只需find函数查找一下就行了

//检查两个节点是否同属一个集合(根节点是否相同)
bool connected(int x, int y)
{return find(x)==find(y);
}

例题

大概就是这个样子了，本算法还是相对模板的，但也很妙！以一道题为例吧：P1111 修复公路 - 洛谷https://www.luogu.com.cn/problem/P1111

大概思路

主线还是进行集合合并以及判断是否全部联通。需要注意的是它要求最快什么时候能全部联通。那么我们就要对修路操作根据时间进行排序。先用结构体将修路信息储存起来并按时间升序排序并逐次判断连通性。如果此时全部联通，直接输出此时时间并退出程序。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
const int M = 1e5+5;
#define int long long
vector<int> parent;
vector<int> Size;
int x,y,t;
int n,m;
struct site
{int a;//连接的两个村庄int b;int t;//修通的时间
}f[M];bool cmp(site a, site b)
{return a.t < b.t;
}void init()
{parent.resize(N);Size.resize(N,1);//初始化 刚开始他们的父节点都是自己for(int i=0; i<N; i++) parent[i]=i;
}int find(int n)//寻找根节点
{if(parent[n]!=n)//路径压缩,将路径上的节点顺手连到根节点parent[n]=find(parent[n]);return parent[n];
}void unit(int x, int y)//将两点联通
{x = find(x);y = find(y);if(x==y) return ;//如果根节点一样就不用链接了if(Size[x]<Size[y])//将小树连到大树上{parent[x] = y;Size[y]+=Size[x];//合并之后数量相加}else{parent[y] = x;Size[x]+=Size[y];}
}bool lian(int x, int y)//判断根节点是否相同
{return find(x)==find(y);
}void solve()
{cin >> n >> m;//村庄数量和公路数量init();//先初始化for(int i=1; i<=m; i++)//先将路径用结构体存起来{cin >> x >> y >> t;f[i].a=x;f[i].b=y;f[i].t=t;}sort(f+1,f+1+m,cmp);//根据修通的时间升序排序int f1=0;for(int i=1; i<=m; i++){unit(f[i].a,f[i].b);if(Size[find(f[i].a)]==n)//如果此时已经将所有的村庄都链接起来了{cout << f[i].t;//就直接是最早时间f1=1;return ;}}if(!f1) cout << -1;//所有路都修完了但是还没有全部通路
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;// cin >> t;while(t--) solve();return 0;
}

OK到这里就结束了，图画的比较简陋，凑合看吧。终于解我心头之恨，爽！不过也说明实在太菜了，当时这都没学到 --_--