并查集进阶（提高）
可持久化并查集（提高）
可持久化并查集是并查集的另一种扩展，它支持回退操作，即可以回到之前的某个状态。
CSP-J 阶段可以暂时不考虑
概念与实现
可持久化并查集通常使用可持久化数据结构（如可持久化线段树或主席树）来实现。基本思想是记录每次操作的变化，以便能够回退到之前的状态。
一种简单的实现方式是使用栈记录每次操作：
const int MAXN = 10005;
int parent[MAXN];
stack<pair<int, int>> history; // 记录操作历史
// 初始化
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
while (!history.empty()) {
history.pop();
}
}
// 查找
int find(int x) {
return parent[x] == x ? x : find(parent[x]);
}
// 合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
history.push({rootX, parent[rootX]}); // 记录变化前的状态
parent[rootX] = rootY;
}
}
// 回退一步
void undo() {
if (!history.empty()) {
auto [node, oldParent] = history.top();
history.pop();
parent[node] = oldParent;
}
}
更复杂的实现可以使用可持久化线段树或主席树，这里不再详述。
在复杂问题中的应用
可持久化并查集常用于需要回退操作的场景，例如：
- 动态图问题：支持边的添加和删除
- 历史查询问题：查询某个历史时刻的连通性
- 回溯算法：在搜索过程中需要回退状态
示例：洛谷P3402 可持久化并查集
这道题目要求支持历史版本查询，可以使用可持久化并查集解决：
// 这里给出一个使用可持久化数组实现的简化版本
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> parent[MAXN]; // 每个版本的父节点数组
vector<int> rank[MAXN]; // 每个版本的秩数组
int version = 0; // 当前版本
// 初始化第一个版本
void init(int n) {
parent[0].resize(n + 1);
rank[0].resize(n + 1);
for (int i = 1; i <= n; i++) {
parent[0][i] = i;
rank[0][i] = 0;
}
}
// 在指定版本中查找
int find(int ver, int x) {
if (parent[ver][x] == x) {
return x;
}
return find(ver, parent[ver][x]);
}
// 创建新版本并合并
void unionSets(int x, int y) {
version++;
parent[version] = parent[version - 1]; // 复制上一版本
rank[version] = rank[version - 1];
int rootX = find(version, x);
int rootY = find(version, y);
if (rootX != rootY) {
if (rank[version][rootX] < rank[version][rootY]) {
parent[version][rootX] = rootY;
} else if (rank[version][rootX] > rank[version][rootY]) {
parent[version][rootY] = rootX;
} else {
parent[version][rootY] = rootX;
rank[version][rootX]++;
}
}
}
// 查询指定版本中x和y是否连通
bool isConnected(int ver, int x, int y) {
return find(ver, x) == find(ver, y);
}
int main() {
int n, m;
cin >> n >> m;
init(n);
for (int i = 0; i < m; i++) {
int op, x, y;
cin >> op;
if (op == 1) {
cin >> x >> y;
unionSets(x, y);
} else if (op == 2) {
cin >> x;
version = x; // 切换到指定版本
} else {
cin >> x >> y;
cout << (isConnected(version, x, y) ? "1" : "0") << endl;
}
}
return 0;
}
并查集与其他数据结构的结合
并查集可以与其他数据结构结合，解决更复杂的问题。
与树状数组结合
并查集与树状数组结合可以解决一些需要快速统计集合信息的问题。
// 并查集与树状数组结合的示例
int parent[MAXN];
int bit[MAXN]; // 树状数组
// 树状数组相关操作
void update(int i, int val) {
while (i < MAXN) {
bit[i] += val;
i += i & -i;
}
}
int query(int i) {
int sum = 0;
while (i > 0) {
sum += bit[i];
i -= i & -i;
}
return sum;
}
// 并查集操作
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
update(rootY, query(rootX)); // 更新树状数组
update(rootX, -query(rootX));
}
}
与线段树结合
并查集与线段树结合可以解决区间合并和查询的问题。
// 并查集与线段树结合的示例
struct SegmentTree {
vector<int> parent; // 每个节点的父节点
void build(int node, int start, int end) {
if (start == end) {
parent[node] = start;
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
parent[node] = parent[2 * node]; // 默认使用左子树的代表元素
}
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
void unionRange(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return;
}
if (l <= start && end <= r) {
// 整个区间都在查询范围内
int root = find(node);
parent[root] = find(1); // 合并到根节点
return;
}
int mid = (start + end) / 2;
unionRange(2 * node, start, mid, l, r);
unionRange(2 * node + 1, mid + 1, end, l, r);
}
};
这些结合使用的例子展示了并查集的灵活性和强大功能。通过与其他数据结构结合，并查集可以解决更广泛的问题，特别是那些需要维护集合信息并支持快速查询的问题。