并查集应用详解：环检测与逻辑推理问题
并查集基础实现要点
在使用并查集时，路径压缩必须正确实现。常见的错误是忘记在查找函数中返回根节点值，这会导致超时（TLE）。推荐的写法如下：
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}该写法通过递归完成路径压缩，将当前节点直接连接至根节点，显著提升后续查询效率。
真假身份推断问题
给定 n 个人和 m 条陈述，每个人要么是"英雄"（诚实者），要么是"反派"（说谎者）。当询问某人他人身份时，"英雄"如实回答，"反派"则颠倒答案。目标是判断最多可能有多少个"英雄"，若矛盾则输出 -1。
采用扩展并查集建模：为每个人 i 创建两个节点——i 表示其为坏人，i+n 表示其为好人。根据陈述内容进行合并：
- 若 A 称 B 为"好人"，则 A 和 B 同类（同好或同坏）→ 合并 (A, B) 与 (A+n, B+n)
- 若 A 称 B 为"坏人"，则 A 和 B 不同类 → 合并 (A, B+n) 与 (A+n, B)
最终检查是否存在某个 i 满足 find(i) == find(i+n)，即同一人同时被判定为好人和坏人，若有则无解。否则对每个连通块取好人/坏人数量的最大值累加即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;
int par[MAXN], cnt[MAXN];
int find(int x) {
if (x != par[x]) {
int root = find(par[x]);
cnt[root] += cnt[x];
cnt[x] = 0;
par[x] = root;
}
return par[x];
}
void merge(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) {
cnt[rb] += cnt[ra];
par[ra] = rb;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
// 初始化
for (int i = 1; i <= 2 * n; ++i) {
par[i] = i;
cnt[i] = (i > n); // i+n 对应好人初始计数为1
}
while (m--) {
int u, v; string res;
cin >> u >> v >> res;
int ru = find(u), rv = find(v);
int ru_n = find(u + n), rv_n = find(v + n);
if (res == "good") {
merge(u, v); // 同类
merge(u + n, v + n);
} else {
merge(u, v + n); // 异类
merge(u + n, v);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (find(i) == find(i + n)) {
cout << -1 << '\n';
return 0;
}
ans += max(cnt[find(i)], cnt[find(i + n)]);
cnt[find(i)] = cnt[find(i + n)] = 0;
}
cout << ans << '\n';
return 0;
}
图中环检测
给定一个网格图操作序列，每次连接两个相邻格子，判断是否形成闭环。利用并查集维护连通性：若两个本已连通的格子再次被连接，则说明出现环。
将二维坐标 (x, y) 映射为一维索引：idx = x * n + y。对于向下或向右的操作，计算对应邻居位置并执行合并判断。
int get_id(int x, int y, int n) {
return x * n + y;
}
// 主循环中
for (int i = 1; i <= m; ++i) {
int x, y; string dir;
cin >> x >> y >> dir;
x--; y--;
int a = get_id(x, y, n);
int b = (dir == "D") ? get_id(x+1, y, n) : get_id(x, y+1, n);
int pa = find(a), pb = find(b);
if (pa == pb) {
cout << i << endl;
return 0;
}
par[pa] = pb;
}
cout << "draw" << endl;
带权并查集：区间奇偶性约束
处理形如"区间 [l, r] 内元素个数为奇数/偶数"的约束条件。使用带边权并查集，其中 d[x] 表示从 x 到根节点路径上权值异或和，用于表示相对奇偶关系。
映射离散化函数 get(x) 将输入坐标映射到紧凑整数域。若两节点已在同一集合，验证现有路径异或结果是否与当前声明一致；否则合并两棵树，并设置新边权使整体满足约束。
unordered_map<int, int> mapping;
int get_coord(int x) {
if (!mapping.count(x)) mapping[x] = ++total_nodes;
return mapping[x];
}
// 边权更新逻辑
if (root_a == root_b) {
if (((dist[a] ^ dist[b]) != expected_parity)) {
result = i - 1; break;
}
} else {
parent[root_a] = root_b;
dist[root_a] = dist[a] ^ dist[b] ^ expected_parity;
}
连通块内属性聚合 + 01 背包
先通过并查集合并物品组，每组合并后体积与价值累加至根节点。随后对每个独立连通块作为整体物品进行 01 背包求解，最大化总价值。
for (int i = 1; i <= n; ++i) {
if (par[i] == i) { // 根节点代表一个连通块
for (int j = capacity; j >= volume[i]; --j) {
dp[j] = max(dp[j], dp[j - volume[i]] + value[i]);
}
}
}
字符串分类问题
若干字符串若含有相同字母则属于同一类。建立并查集，遍历每个字符串中的字符，若某字母曾出现在之前字符串中，则将其所属字符串与当前字符串合并。
int last_occurrence[26] = {}; // 记录各字母最后出现的字符串编号
for (int i = 1; i <= n; ++i) {
string s; cin >> s;
for (char c : s) {
int idx = c - 'a';
if (last_occurrence[idx]) {
merge(last_occurrence[idx], i);
} else {
last_occurrence[idx] = i;
}
}
}
// 统计根节点数量即为类别数
