写在前面
并查集是一种树形的数据结构。
并查集能维护连通性，传递性。通俗的说：亲戚的亲戚是亲戚。
并查集一般支持两个操作：查询两个元素是否在同一个联通块内，合并两个联通块。
普通并查集
来道例题
初始化
初始状态下每个元素只与自己联通，我们用 (fa_i) 表示 (i) 所处联通块内的根节点，显然初始化 (fa_i = i)。
寻找根节点
不断跳 (fa) 即可。
代码只有一行：
int Find(int x) { return fa[x] == x ? x : Find(fa[x]); }
复杂度 (O(n)).
合并
假设我们要合并 (u,v)。显然只需要让 (u,v) 所在联通块内的点都指向同一个根节点即可。
我们可以先找到 (u,v) 所在的根节点 (uf, vf)，然后使 (fa_{uf} = vf)，这样所有的点指向的跟结点就均为 (vf)。
Code:
void Hb(int x, int y) {
int xf = Find(x), yf = Find(y);
if(xf != yf) fa[xf] = yf;
}
复杂度 (O(n))
查询
也比较简单，看看两个元素的根节点是否相同即可。
Code：
bool Check(int x, int y) { return Find(x) == Find(y); }
复杂度 (O(n))。
路径压缩
按照上面的方法操作，如果出题人特意构造数据，会把我们卡成 (O(n^2))。
我们考虑优化一下，让每个元素直接指向它的根节点，免去跳多步的麻烦。
优化后代码：
int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
稍微一改即可。
带权并查集
看道例题 P4079 [SDOI2016]齿轮
对每个结点另存一个值 (k_u = 1)。
当 (u,v) 之间出现传动比关系时，令 (fa_u = v)，且 (k_u = frac{x}{y})。
同样带权并查集也可以进行路径压缩。
若使 (fa_u = fa_{fa_u})，则 (k_u = k_u imes k_{fa})
联通块合并：
已知 (k_u,k_v)，现在要连接 (u,v)，即 (k_u^, = frac{x}{y})，我们要让 (fa_u o fa_v)，设值为 (k_{fa_u})。
因为要保证转动比合法且不变。所以 (k_u imes k_{fa_u} = f_u^, imes f_v)，解得 (k_{fa_u} = frac{f_u^, imes f_v}{k_u})。
同一联通块内的两点判断是否有解：看看这个式子是否成立即可 (k_u imes k_{fa_u} = f_u^, imes f_v)。
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const double lim = 1e-10;
int T, n, m;
int fa[1010];
double k[1010];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int Find(int x) {
if(fa[x] == x) return x;
int tmp = Find(fa[x]); // 带权并查集路径压缩
k[x] *= k[fa[x]];
return fa[x] = tmp;
}
int main()
{
T = read(); int cnt = 0;
while(++cnt <= T) {
n = read(), m = read();
for(int i = 1; i <= n; ++i) fa[i] = i, k[i] = 1.00;
bool flag = false;
for(int i = 1, u, v, x, y; i <= m; ++i) {
u = read(), v = read(), x = read(), y = read();
int uf = Find(u), vf = Find(v);
if(uf != vf) {
fa[uf] = vf;
k[uf] *= (1.0 * x * k[v]) / (1.0 * y * k[u]);
} else {
double K = (k[u] / k[v]);
if(abs(K - (1.0 * x / y)) > lim) flag = true;
}
}
if(flag) printf("Case #%d: No
", cnt);
else printf("Case #%d: Yes
", cnt);
}
return 0;
}
种类并查集
两道例题：P1525 [NOIP2010 提高组] 关押罪犯， P2024 [NOI2001] 食物链。
在这种情况下，我们需要维护这样一种关系：
敌人的敌人是朋友。
常见的做法是将原并查集扩大一倍规模，并划分为两个种类。
在同个种类的并查集中合并，和原始的并查集没什么区别，仍然表达他们是朋友这个含义。
考虑在不同种类的并查集中合并的意义，其实就表达 他们是敌人 这个含义了。
按照并查集美妙的 传递性，我们就能具体知道某两个元素到底是 敌人 还是 朋友 了。
至于某个元素到底属于两个种类中的哪一个，由于我们不清楚，因此两个种类我们都试试。
如果是食物链这道题，我们应该把原并查集扩大三倍规模。只有敌人的敌人的敌人才是朋友。修改的时候也要同时修改三个种类之间的关系。我们也可以继续推广到更大的规模。
放一下两个例题的代码：
关押罪犯 Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 2e4+4;
const int MAXM = 1e5+5;
struct edge{
int from, to, w;
bool operator < (const edge &b) const {return w < b.w; }
}e[MAXM];
int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
return s * w;
}
int n, m;
int fa[MAXN << 1];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main()
{
n = read(), m = read();
for(int i = 1; i <= 2 * n; ++i) fa[i] = i;
for(int i = 1; i <= m; ++i){
e[i].from = read(), e[i].to = read(), e[i].w = read();
}
sort(e + 1, e + m + 1);
for(int i = m; i >= 0; --i){
int uf = find(e[i].from), vf = find(e[i].to);
if(uf == vf) {
printf("%d", e[i].w);
break;
}
else{
fa[find(e[i].from)] = find(e[i].to + n);
fa[find(e[i].to)] = find(e[i].from + n);
}
}
return 0;
}
食物链 Code：
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e6+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
struct edge {
int from, to, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 1;
int n, k, Ans = 0;
int fa[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
int main()
{
// freopen("P2024_2.in","r",stdin);
n = read(), k = read();
for(int i = 1; i <= 3 * n; ++i) fa[i] = i;
for(int i = 1, opt, x, y; i <= k; ++i) {
opt = read(), x = read(), y = read();
if(x > n || y > n) { Ans++; continue; }
if(opt == 1) {
if(Find(x + n) == Find(y) || Find(x) == Find(y + n)) Ans++;
else {
fa[Find(x)] = Find(y);
fa[Find(x + n)] = Find(y + n);
fa[Find(x + 2 * n)] = Find(y + 2 * n);
}
} else {
if(Find(x) == Find(y) || Find(x) == Find(y + n)) Ans++;
else {
fa[Find(x + n)] = Find(y);
fa[Find(x + 2 * n)] = Find(y + n);
fa[Find(x)] = Find(y + 2 * n);
}
}
}
printf("%d", Ans);
return 0;
}