并查集的基本概念

并查集（Disjoint Set Union，DSU）是一种用于管理元素分组的数据结构，支持两种核心操作：

• 查找（Find）：确定元素所属的集合（通常通过根节点表示）。
• 合并（Union）：将两个集合合并为一个。

其底层逻辑基于树结构，通过路径压缩和按秩合并优化效率，使得操作接近常数时间复杂度。

---

底层实现逻辑

数据结构

使用数组parent[]表示每个节点的父节点，初始化时每个节点自成一集合（parent[i] = i）。

int parent[MAX_SIZE];  // 父节点数组  
int rank[MAX_SIZE];    // 秩（树高度）  

void init(int n) {  
    for (int i = 0; i < n; i++) {  
        parent[i] = i;  
        rank[i] = 0;  
    }  
}  

查找（Find）

递归或迭代找到根节点，同时应用路径压缩优化（直接指向根节点，降低树高度）。

int find(int x) {  
    if (parent[x] != x) {  
        parent[x] = find(parent[x]);  // 路径压缩  
    }  
    return parent[x];  
}  

合并（Union）

按秩合并：将秩较小的树合并到秩较大的树下，避免树过高。

void unionSets(int x, int y) {  
    int rootX = find(x);  
    int rootY = find(y);  
    if (rootX != rootY) {  
        if (rank[rootX] < rank[rootY]) {  
            parent[rootX] = rootY;  
        } else if (rank[rootX] > rank[rootY]) {  
            parent[rootY] = rootX;  
        } else {  
            parent[rootY] = rootX;  
            rank[rootX]++;  
        }  
    }  
}  

---

应用场景

1. 连通性问题

• 动态连通性：判断图中两个节点是否连通（如Kruskal算法中的边处理）。
• 社交网络：快速合并好友关系分组。

2. 最小生成树（Kruskal算法）

通过并查集高效判断边的两个顶点是否属于同一集合，避免环的形成。

3. 图像处理

像素区域合并，标记连通区域。

4. 游戏开发

网格地图中动态连接的区块管理（如迷宫生成）。

---

完整代码示例

#include <stdio.h>  
#define MAX_SIZE 100  

int parent[MAX_SIZE];  
int rank[MAX_SIZE];  

void init(int n) {  
    for (int i = 0; i < n; i++) {  
        parent[i] = i;  
        rank[i] = 0;  
    }  
}  

int find(int x) {  
    if (parent[x] != x) {  
        parent[x] = find(parent[x]);  
    }  
    return parent[x];  
}  

void unionSets(int x, int y) {  
    int rootX = find(x);  
    int rootY = find(y);  
    if (rootX != rootY) {  
        if (rank[rootX] < rank[rootY]) {  
            parent[rootX] = rootY;  
        } else {  
            parent[rootY] = rootX;  
            if (rank[rootX] == rank[rootY]) {  
                rank[rootX]++;  
            }  
        }  
    }  
}  

int main() {  
    int n = 10;  
    init(n);  
    unionSets(1, 2);  
    unionSets(2, 3);  
    printf("Find(3): %d\n", find(3));  // 输出应为1的根  
    return 0;  
}  

通过路径压缩和按秩合并，并查集的均摊时间复杂度接近 o(1)。

扩展域并查集原理

扩展域并查集通过将元素拆分为多个逻辑部分（域）来处理复杂关系。常见场景是处理具有对立或依赖关系的元素，例如朋友与敌人、染色问题等。每个元素被拆分为多个虚拟节点，通常为原始元素的倍数关系。

逻辑核心在于通过合并不同域表达元素间的关系。例如处理敌对关系时，若元素A与B敌对，则将A的朋友域与B的敌人域合并，A的敌人域与B的朋友域合并。这种拆分使得关系传递性得以维护。

带权并查集原理

带权并查集在普通并查集基础上增加权值数组，记录节点与父节点之间的关系。权值通常表示相对关系，如距离、差值或模数。路径压缩和合并操作需同步维护权值以保证关系正确性。

核心操作包含权值的传递与合并。路径压缩时，权值需按路径叠加更新；合并集合时，需根据关系计算新权值。例如处理模运算关系时，权值表示与父节点的差值模某个数。

扩展域并查集C代码

#include <stdio.h>
#define MAXN 10000

int parent[MAXN * 2]; // 每个元素拆分为2个域

void init(int n) {
    for (int i = 0; i < 2 * n; i++) {
        parent[i] = i;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void merge(int x, int y) {
    parent[find(x)] = find(y);
}

// 示例：处理敌对关系
void add_enemy(int a, int b, int n) {
    merge(a, b + n); // a的朋友与b的敌人合并
    merge(a + n, b); // a的敌人与b的朋友合并
}

int is_friend(int a, int b) {
    return find(a) == find(b);
}

int is_enemy(int a, int b, int n) {
    return find(a) == find(b + n);
}

带权并查集C代码

#include <stdio.h>
#define MAXN 10000

int parent[MAXN];
int weight[MAXN]; // 权值数组

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        weight[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x) {
        int old_parent = parent[x];
        parent[x] = find(parent[x]);
        weight[x] += weight[old_parent]; // 路径压缩时更新权值
    }
    return parent[x];
}

void merge(int x, int y, int w) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        parent[root_x] = root_y;
        weight[root_x] = weight[y] - weight[x] + w; // 根据关系计算新权值
    }
}

// 示例：查询x与y的关系
int query(int x, int y) {
    if (find(x) != find(y)) {
        return -1; // 无关系
    }
    return weight[x] - weight[y];
}

关键逻辑对比

扩展域通过拆分节点表达多元关系，适合离散型关系处理。带权并查集通过数值维护连续关系，适合计算型问题。两者均需在合并与查询时维护关系正确性，扩展域的空间复杂度更高，带权并查集的时间复杂度更优。

实际应用中，扩展域适合明确对立关系场景（如二分图检测），带权并查集适合数值传递场景（如差分约束）。代码实现时需注意初始化范围和权值更新方向。

例题：洛谷P1525 [NOIP 2010 提高组] 关押罪犯

扩展域并查集解决关押罪犯问题

问题描述 NOIP关押罪犯问题描述为：将N个罪犯分配到两个监狱，使得同一监狱内1的罪犯之间的冲突值尽可能小。需要找到一种分配方案，使得最大冲突值最小。

扩展域并查集思路 扩展域并查集通过将每个元素拆分为多个域（通常为2个）来表示不同的关系状态。在本题中，每个罪犯可以拆分为“在A监狱”和“在B监狱”两个域。

实现步骤

定义并查集数组fa，大小为2*N，其中1..N表示在A监狱，N+1..2*N表示在B监狱。

初始化并查集，每个元素的父节点为自己：

for(int i=1; i<=2*N; i++) fa[i] = i;

处理冲突关系时，对于每对罪犯(x,y)和冲突值c：

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

将冲突关系按冲突值从大到小排序，依次处理：

sort(edges.begin(), edges.end(), [](auto &a, auto &b){
    return a.c > b.c;
});

for(auto &e : edges) {
    int x = e.x, y = e.y, c = e.c;
    if(find(x) == find(y)) {
        // 找到无法避免的冲突
        cout << c << endl;
        return;
    }
    // 将x和y分配到不同监狱
    merge(x, y+N);
    merge(x+N, y);
}

完整代码示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 2e4+5;
int fa[MAXN*2];

struct Edge {
    int x, y, c;
};

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    
    for(int i=1; i<=2*N; i++) fa[i] = i;
    
    for(int i=0; i<M; i++) {
        cin >> edges[i].x >> edges[i].y >> edges[i].c;
    }
    
    sort(edges.begin(), edges.end(), [](auto &a, auto &b){
        return a.c > b.c;
    });
    
    for(auto &e : edges) {
        int x = e.x, y = e.y, c = e.c;
        if(find(x) == find(y)) {
            cout << c << endl;
            return 0;
        }
        merge(x, y+N);
        merge(x+N, y);
    }
    
    cout << 0 << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(Mα(N))，其中α为反阿克曼函数
• 空间复杂度：O(N)

注意事项

1. 扩展域的大小需要足够（通常是原问题的2倍）
2. 冲突关系需要按冲突值从大到小处理
3. 当发现两个罪犯必须在同一监狱时，当前冲突值即为答案