并查集(DSU)
并查集是一种常用的数据结构，可以高效地处理动态连通性问题。在例题中，通过拓展并查集的应用，我们可以解决一些特殊的问题，如带权并查集和种类并查集。
P1196 [NOI2002] 银河英雄传说
思路很简单，用并查集维护连通性的同时维护每个舰队到列首的距离即可。
由于并查集的修改操作只对集合的最早祖先进行修改（维护集合中元素总数可以完成这项操作），我们在对非最早祖先元素操作时，需要先由该元素当前记录下的祖先到列首的距离以及该元素到当前记录下的祖先的距离推出，这一部分操作可以在路径压缩中递归完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int fa[maxN + 5], val[maxN + 5], sum[maxN + 5];
int find(int x) {
if (x == fa[x])
return x;
else {
int fx = find(fa[x]);
val[x] += val[fa[x]];
fa[x] = fx;
return fa[x];
}
}
int join(int i, int j) {
int fi = find(i), fj = find(j);
fa[fi] = fj;
val[fi] = sum[fj];
sum[fj] += sum[fi];
}
int main() {
ios;
rep(i, 1, maxN) fa[i] = i, sum[i] = 1;
int T;
cin >> T;
while (T--) {
char op;
int i, j;
cin >> op >> i >> j;
if (op == 'M') {
join(i, j);
} else {
if (find(i) == find(j))
cout << abs(val[i] - val[j]) - 1 << endl;
else
cout << "-1\n";
}
}
return 0;
}
CF1850H
题目大意
有 $n$ 个军队部署在一条直线上，有 $m$ 个要求，每个要求为军队 $a$ 要在军队 $b$ 的前面 $d$ 格位置处，问是否能有一种放置方案满足所有要求。
题解
带权并查集模板题，用带权并查集维护每个点在它的祖先前面多少格即可，$i,j$ 两点间距离可用 $dist[i]-dist[j]$ 表示。维护带权并查集的普遍方法：由于并查集在合并的时候只更改祖先，只需要先对祖先进行维护，集合里的其它点在路径压缩的时候可以通过递归完成维护。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int fa[maxN + 5], dist[maxN + 5];
int find(int x) {
if (x == fa[x])
return x;
else {
int fx = find(fa[x]);
dist[x] += dist[fa[x]];
fa[x] = fx;
return fa[x];
}
}
void join(int x, int y, int val) {
int fx = find(x), fy = find(y);
fa[fx] = fy;
dist[fx] = val + dist[y] - dist[x];
}
void solve() {
int n, m, ok = 1;
cin >> n >> m;
rep(i, 1, n) fa[i] = i, dist[i] = 0;
rep(i, 0, m - 1) {
int a, b, d;
cin >> a >> b >> d;
if (!ok)
continue;
if (find(a) != find(b)) {
join(a, b, d);
} else {
if (dist[a] - dist[b] != d) {
ok = 0;
cerr << i << endl;
}
}
}
if (ok)
cout << "YES\n";
else
cout << "NO\n";
}
P2024 [NOI2001] 食物链
种类并查集(拓展域)
并查集能维护连通性、传递性，通俗地说，亲戚的亲戚是亲戚。然而当我们需要维护一些对立关系，比如敌人的敌人是朋友时，正常的并查集就很难满足我们的需求。这时，种类并查集就诞生了。常见的做法是将原并查集扩大一倍规模，并划分为两个种类。
在同个种类的并查集中合并，和原始的并查集没什么区别，仍然表达他们是朋友这个含义。考虑在不同种类的并查集中合并的意义，其实就表达他们是敌人这个含义了。
按照并查集美妙的传递性，我们就能具体知道某两个元素到底是敌人还是朋友了。至于某个元素到底属于两个种类中的哪一个，由于我们不清楚，因此两个种类我们都试试。
具体实现，详见 P1525 关押罪犯。
类似的，对于这道题，我们维护三个种类，具体为某个物种、它的天敌、它的猎物，维护一个扩大两倍规模的并查集即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int N, k, fa[3 * maxN + 5], ans;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main() {
ios;
rep(i, 1, 3 * maxN) fa[i] = i;
cin >> N >> k;
rep(i, 0, k - 1) {
int op, x, y;
cin >> op >> x >> y;
if (x > N || y > N)
ans++;
else {
if (op == 1) {
if (find(y) != find(x + N) && find(y) != find(x + 2 * N)) {
fa[find(y)] = find(x);
fa[find(y + N)] = find(x + N);
fa[find(y + 2 * N)] = find(x + 2 * N);
} else
ans++;
} else {
if (find(x) != find(y) && find(x) != find(y + 2 * N)) {
fa[find(x)] = find(y + N);
fa[find(x + N)] = find(y + 2 * N);
fa[find(x + 2 * N)] = find(y);
} else
ans++;
}
}
}
cout << ans << endl;
return 0;
}