c
casperwu
V1
2022/07/16阅读:14主题:橙心
并查集
并查集
1. 常用操作与优化
-
合并两个集合 -
查询某个元素的祖宗节点 -
在查询的过程中可以做路径压缩操作
2. 使用场景
常用于具有传递性质的题目中,并且传递具有双向性,即可以理解为无向图关系。
3. 例题

3.1 题意理解
使用前缀和思想: Si 表示前i个数中1的个数则 S[l~r] 中有奇数个1 de等价于 S[r] - S[l-1] 为奇数 等价于 S[r] 与 S[l-1] 的奇偶性不同;同理可推, S[l-r] 中有偶数个1 等价于 S[r] 与 S[l-1] 的奇偶性相同。
因此可以将题意简化为: 给定两个以及经它们之间的奇偶性,根据给定的条件判断是否有矛盾。
3.2 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 20004;
int fa[N]; // 并查集数组
int d[N]; // 维护到到根节点的距离
unordered_map<int, int> s; // 用于离散化点
int n, m;
int find(int x) {
if(x != fa[x]) {
int root = find(fa[x]);
// 在模 2 的状态下, 加法等价于 异或运算
d[x] ^= d[fa[x]];
fa[x] = root;
}
return fa[x];
}
int get(int x) {
if(s.count(x) == 0) s[x] = ++n;
return s[x];
}
int main() {
cin >> n >> m;
n = 0;
// 并查集初始化
for(int i = 0; i < N; i++) fa[i] = i;
int ans = m;
for(int i = 1; i <= m; i++) {
int a, b;
string op;
cin >> a >> b >> op;
// 使用类似前缀和思想, 因此 b 需要 -1
a = get(a - 1), b = get(b);
int t = 0;
if(op == "odd") t = 1;
int pa = find(a), pb = find(b);
if(pa == pb) {
if((d[a] ^ d[b]) != t) {
ans = i - 1;
break;
}
} else {
fa[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}
}
cout << ans;
return 0;
}
作者介绍
c
casperwu
V1