[算法学习笔记] 并查集
提示：本文并非并查集模板讲解，是在模板基础上的进一步理解以及拓展。
Review
并查集可以用来维护集合问题。例如，已知 \(a,b\) 同属一个集合，\(b,c\) 同属一个集合。那么 \(a,b,c\) 都属一个集合。
并查集分为 合并，查询 操作。定义 \(fa_i\) 表示点 \(i\) 的父亲。为了降低复杂度，在 find 操作向上递归查祖先时我们同步将 \(fa_i\) 更改为 \(i\) 的祖先。这就是所谓路径压缩。
对于合并，为了方便直接合并即可。当然也可以按秩合并优化，虽然我认为优化效果不大。
种类并查集
并查集的传递性非常强大，对于普通的传递关系问题，并查集可以轻松解决。但是，对于有种类关系的，比如"敌人的敌人是朋友” 此类关系又该如何维护呢？
我们来看一到例题。
BOI2003 团伙
Description
现在有 \(n\) 个人，他们之间有两种关系：朋友和敌人。我们知道：
- 一个人的朋友的朋友是朋友
- 一个人的敌人的敌人是朋友
现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。
不难发现，本题的关键在于维护 “敌人的敌人是朋友” 这种关系。如果没有这层限制，那本题就是朴素的并查集模板题。
实际上，我们只需要开两倍并查集。对于 \(\forall x,y\) ，若 \(x,y\) 是朋友，合并 \(x,y\) 即可。这是普通并查集操作。反之，若 \(x,y\) 是敌人，分别合并 \(x,y+n\),\(x+n,y\) 即可。这样我们就解决了问题。
接下来我们将通过画图，来解释这样的合并方式是如何工作的。
模拟样例：已知 \(1,2\) 是敌人关系，\(2,4\) 是敌人关系。按照要求，\(1,4\) 应是朋友关系。\(n=4\)
不难发现，\(4\) 通过敌人 \(2\) ，\(2\) 与敌人 \(1\) 。\(4\) 与 \(1\) 在同一种类里相连，朋友关系。这就是最简单的种类并查集的工作原理。
这样，我们就解决了本题。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int fa[N];
int dist[N];
int ans = 0;
vector <int> Edge;
void Init()
{
for(int i=1;i<=n*2;i++)
{
fa[i] = i;
dist[i] = 1;
}
}
int find(int x)
{
if(x == fa[x]) return x;
fa[x] = find(fa[x]);
return fa[x];
}
void merge(int i,int j)
{
int x = find(i),y = find(j);
if(x == y) return;
if(dist[x] < dist[y]) fa[x] = fa[y];
else fa[y] = fa[x];
if(dist[x] == dist[y] && x != y) dist[y] ++;
}
int main()
{
// freopen("input.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
Init();
for(int i=1;i<=m;i++)
{
char op;
int p,q;
cin>>op>>p>>q;
if(op == 'F')
{
merge(p,q);
}
else
{
merge(p,q+n);
merge(q,p+n);
}
}
for(int i=1;i<=n;i++)
{
// int f = find(i);
if(fa[i] == i) ans ++;
}
cout<<ans<<endl;
return 0;
}
待更。