因为是学习记录，所以知识讲解+例题推荐+练习题解都是放在一起的qvq
普通的并查集+路径压缩相信大家还是会的，就主要是两个操作：
查询某个元素属于哪个集合
合并两个集合成为一个大集合
提出一点，就是求最小生成树的Kruskal算法也是在使用并查集后才是完整的Kruskal
洛谷P2330 [SCOI2005]繁忙的都市 （Kruskal最小生成树）
洛谷P2814 家谱 （字符串+并查集）
洛谷P3958 奶酪 （并查集或搜索）
洛谷P2661 信息传递 （并查集）
洛谷P6121 [USACO16OPEN]Closing the Farm G （上一道题的数据加强版，思路挺巧的，好题qvq）
洛谷P1955 程序自动分析 （离散化+种类并查集，没有离散化数据无情giao崩程序QAQ，算普通并查集中的较难题）
如果你在洛谷或其他OJ上独立做过了几道并查集的题，那么可以接触升级版的并查集了：带权并查集、种类并查集
在这里讨论一下种类并查集（因为带权并查集还没有学）
种类并查集：即在普通并查集“亲戚的亲戚也是亲戚”的基础上再进行一些“分类”，但是这个分类呢并不是根据物品的种类来进行分类，而是类似“敌人的敌人是朋友”的分类（并没有说明“朋友的敌人是我的敌人”！要根据具体题目分析）
种类并查集常规套路：不是开多个或多维并查集数组，而是扩大并查集规模
举个栗子：我们要维护朋友和敌人这两个关系，则将普通并查集的规模扩大两倍，原来的1n还是存放朋友关系，但是n+12n则是存放敌人关系，然后每次操作都分别维护
洛谷P1892 团伙 （基础种类并查集）
洛谷P2024 食物链 （上文说到的三种循环关系的例题，值得做）
洛谷P1525 关押罪犯 （转换一下题目就是种类并查集，思路比较巧）
洛谷P1196 银河英雄传说 （带权并查集，题解先咕着，我也还没做，逃~）
题目请大家直接点开看，因为描述很清晰就不再赘述了，直接来讲思路（这题就是思维难度大，容易绕晕QAQ）
判断是否是假话，其实就是判断当前给出的条件是否与之前构建的并查集关系树冲突，冲突则是假话（于是转换了题目后，就变成维护种类并查集）
我们需要维护三种关系：“同类”、“猎物”、“天敌”，所以扩大三倍规模，第一倍维护同类、第二倍维护猎物、第三倍维护天敌
搞清楚三种关系的传递：猎物的猎物是天敌、天敌的猎物是同类、同类的猎物是猎物、同类的天敌是天敌（反正就是A吃B，B吃C，C吃B）
判断是假话的三条规则：①当前给出x、y是同类，但前面已经构建x、y是天敌关系，是假话；②当前给出x是y的天敌，但前面已经构建x、y是同类或y是x的天敌，是假话；③x、y的编号超出了食物链的最大编号（简单明了）
好了，思路如上，我们可以开始敲代码了quq：
#include <bits/stdc++.h>
using namespace std;
int n,k,u,v,op,ans,fa[150010];
inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main() {
scanf("%d%d",&n,&k);
for(register int i=1;i<=3*n;i++) fa[i]=i; //扩大三倍规模
for(register int i=1;i<=k;i++) {
scanf("%d%d%d",&op,&u,&v);
if(u>n||v>n) { //不存在于食物链中，假话
ans++;
continue;
}
if(op==1) { //如果两者是同类
if(find(u)==find(v+n)||find(u+n)==find(v)) { //如果两者已经是天敌关系，假话
ans++;
continue;
}
fa[find(u)]=find(v); //合并
fa[find(u+n)]=find(v+n);
fa[find(u+n+n)]=find(v+n+n);
}
else { //如果x是y天敌
if(find(u)==find(v)||find(u)==find(v+n)) { //如果两者已经是同类或y是x天敌，假话
ans++;
continue;
}
fa[find(u)]=find(v+n+n); //注意一下对应关系！
fa[find(u+n)]=find(v);
fa[find(u+n+n)]=find(v+n);
}
}
printf("%d",ans);
return 0;
}
题目简述一下：给定n个罪犯，m个关系；对于每个关系给出两个罪犯在同一所监狱中的怨气值；要求将所有罪犯分到两所监狱，要让这两所监狱中所有怨气值的最大值最小
现在来讲思路：
首先我们可以想到贪心，怎么贪？即将所有怨气值从大到小排序，然后首先将怨气值大的分开，直到不能这么干
但我们始终需要维护两所监狱中的怨气值，所以我们不妨将种类并查集作为解题主体再加上排序作为辅助
怎么种类并查集？首先还是先排序，如果当前罪犯x的敌人为空，则将当前关系对应的罪犯y设为x的敌人；之后再遇到罪犯x与其他罪犯z有怨气关系时，就将罪犯z与罪犯y建立朋友关系（“敌人的敌人是朋友”的思想）
你可能会疑惑，罪犯y和罪犯z也有可能是互相的敌人啊，怎么就构建朋友关系了呢？可如果全部处理成敌人关系我们将无法解决这道题，但是转换一下思路，我们已经将怨气值从大到小排序，所以怨气值大的看做敌人，之后再遇到敌人就将两个敌人合并为朋友
这并不与在m个关系的描述中罪犯y与罪犯z是敌人相冲突，因为y与z的怨气值小于x与y的怨气值，不会妨碍我们最终求得怨气值的最大值最小
如果在处理过程中找到了一组罪犯u和罪犯v，满足两人在同一集合中，就直接输出u和v的怨气值
如果处理完所有关系都没有输出，则输出0（题目要求的，因为忘了写，白白WA了一个点）
感觉讲得有点绕QAQ，大家在草稿本上手模一下样例应该就懂了，下面给出代码：
#include <bits/stdc++.h>
using namespace std;
int n,m,fa[400010];
struct node {
int u,v,w;
} a[400010];
inline bool cmp(node x,node y) {
return x.w>y.w;
}
inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=2*n;i++) fa[i]=i; //扩大两倍规模：一倍存朋友，二倍存敌人
for(register int i=1;i<=m;i++) {
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+1,a+1+m,cmp); //怨气值从大到小排序
for(register int i=1;i<=m;i++) {
if(find(a[i].u)==find(a[i].v)) { //找到了最大值最小的怨气值
printf("%d",a[i].w);
return 0;
}
if(find(a[i].u+n)==a[i].u) { //如果还没有敌人，将当前关系对应的罪犯标记为敌人
fa[a[i].u+n]=a[i].v;
}
else if(find(a[i].u+n)!=a[i].u) { //如果有敌人了，则将之前的敌人与现在的敌人合并为朋友
fa[find(a[i].u+n)]=find(a[i].v);
}
if(find(a[i].v+n)==a[i].v) { //双向的
fa[a[i].v+n]=a[i].u;
}
else if(find(a[i].v+n)!=a[i].v) {
fa[find(a[i].v+n)]=find(a[i].u);
}
}
puts("0"); //没有找到，输出0
return 0;
}
说在前面：
这道题因为蒟蒻只会map实现离散化，但是这道题第二个点还是会T，只有90pts（吸氧倒是能A掉）所以各位dalao可以跳过这道题的题解，以下讲的是90pts 的做法，抱歉啊！
题目请大家点击上面的链接查看，不多赘述，直接讲思路
这题就是普通的并查集，但是数据太大了，直接存放肯定炸得体无完肤，所以我们需要引入“离散化”来存放数据
离散化大致有两种：
（1）去重（可以用到unique去重函数）+ 排序 +二分索引（可以用到lower_bound函数）
（2）Hash表（散列表）：如果维护的好，可以实现O(1)的查询
下面给出蒟蒻的90pts代码：
#include <bits/stdc++.h>
using namespace std;
bool pd;
int t,n,i,e[2000010];
map<long long ,long long> a; //用map实现离散化（第二个点会T）
long long tot,u[2000010],v[2000010],fa[2000010];
inline long long find(long long x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
tot=0;
pd=false;
for(i=1;i<=n;i++) {
scanf("%lld%lld%d",&u[i],&v[i],&e[i]);
if(a[u[i]]==0) a[u[i]]=++tot; //离散化
if(a[v[i]]==0) a[v[i]]=++tot;
}
for(i=1;i<=tot;i++) fa[i]=i;
for(i=1;i<=n;i++) { //先处理合并（相等）的情况
if(e[i]==1) {
fa[find(a[u[i]])]=find(a[v[i]]);
}
}
for(i=1;i<=n;i++) {
if(e[i]==0) { //遇到不相等的情况我们再判断是否合法
if(find(a[u[i]])==find(a[v[i]])) {
pd=true; //不合法打上标记就可以直接跳出了
break;
}
}
}
if(pd==true) puts("NO");
else puts("YES");
a.clear(); //记得清空
}
return 0;
}
说在前面：
这道题A了，但是数据加强版的我还没过（准确来说应该是还没做，嘘）
就讲讲低配版的思路：
题目要求按顺序关闭谷仓，每次关闭都要判断当前剩余所有谷仓是否联通
我们转换一下，将顺序关闭改为倒序开启！，每一次开启就相当于插入一个点，我们进行维护（普通）并查集即可
下面给出注释及其水的代码（写累了，下次补上）：
#include <bits/stdc++.h>
using namespace std;
int n,m,fa[3010],ans[3010],flag[3010],order[3010];
struct node {
int u,v;
}a[3010];
inline int find_fa(int x) {
if(fa[x]==x) return x;
return fa[x]=find_fa(fa[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
scanf("%d%d",&a[i].u,&a[i].v);
}
for(register int i=1;i<=n;i++) {
fa[i]=i;
scanf("%d",&order[i]); //输入关闭顺序
}
for(register int i=n;i>=1;i--) { //处理成倒序开启
flag[order[i]]=1; //flag[i]表示i是否在集合中
for(register int j=1;j<=m;j++) {
if(flag[a[j].u]==1&&flag[a[j].v]==1) {
int x=find_fa(a[j].u);
int y=find_fa(a[j].v);
if(x!=y) fa[x]=y;
}
}
for(register int j=1;j<=n;j++) { //判断是否联通
if(find_fa(j)==j&&flag[j]==1) ans[i]++; //ans[i]存储第i次询问时并查集中有多少个集合
}
}
for(register int i=1;i<n;i++) {
if(ans[i]==1) puts("YES");
else puts("NO");
}
puts("YES");
return 0;
}
原文：https://www.cnblogs.com/Eleven-Qian-Shan/p/13154721.html