博客详情 - 42OJ

admin 的博客
acm003 并查集与最小生成树算法详解
admin LV 1 SU @ 2025-11-17 10:45:42

1. 并查集(Disjoint Set)基础

1.1 并查集的概念

并查集是一种用于管理元素分组情况的数据结构，主要支持两种操作：

合并(Union)：将两个元素所在的集合合并为一个集合
查找(Find)：查找某个元素所属的集合代表

1.2 并查集的核心思想

用集合中的某个元素来代表整个集合，就像每个班级有一个班长代表整个班级。

1.3 并查集的两种实现方式

方式一：扁平化结构（直接存储代表元素）

// 初始化：每个元素都是自己的代表
void init(int set[], int n) {
    for (int i = 1; i <= n; i++) {
        set[i] = i;
    }
}

// 查找：直接返回代表元素
int find(int set[], int x) {
    return set[x];
}

// 合并：需要遍历所有元素
void merge(int set[], int a, int b, int n) {
    int repA = find(set, a);
    int repB = find(set, b);
    if (repA != repB) {
        // 将repB所在集合的所有元素改为repA
        for (int i = 1; i <= n; i++) {
            if (set[i] == repB) {
                set[i] = repA;
            }
        }
    }
}

时间复杂度分析：

查找：O(1)
合并：O(n)

方式二：树状结构（存储父节点）

// 初始化：每个元素都是自己的根
void init(int parent[], int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}

// 查找：沿着父节点找到根
int find(int parent[], int x) {
    int r = x;
    while (parent[r] != r) {  // 不是根节点就继续向上找
        r = parent[r];
    }
    return r;
}

// 合并：将一个集合的根指向另一个集合的根
void merge(int parent[], int a, int b) {
    int rootA = find(parent, a);
    int rootB = find(parent, b);
    if (rootA != rootB) {
        parent[rootA] = rootB;  // 或 parent[rootB] = rootA;
    }
}

时间复杂度分析：

查找：最坏O(n)，平均O(log n)
合并：O(1)

2. 并查集的应用实例

2.1 城镇连通问题（HDU 1232）

问题描述：有n个城镇，给出m条道路连接情况，求最少还需要修建多少条道路才能使所有城镇连通。

解决方案：最终连通分量数减1就是需要修建的道路数。

#include <iostream>
using namespace std;

const int MAXN = 1005;
int parent[MAXN];

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

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

void merge(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

int main() {
    int n, m;
    while (cin >> n && n) {
        cin >> m;
        init(n);
        
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            merge(a, b);
        }
        
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) {  // 统计根节点数量
                count++;
            }
        }
        
        cout << count - 1 << endl;
    }
    return 0;
}

2.2 判断图是否构成树（HDU 1272）

问题描述：判断一个无向图是否是一棵树（连通且无环）。

解决方案：

对于每条边，如果两个顶点已经在同一集合，说明有环
最后检查是否只有一个连通分量

bool isTree(int edges[][2], int n, int m) {
    init(n);
    
    for (int i = 0; i < m; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        
        if (find(a) == find(b)) {
            return false;  // 有环
        }
        merge(a, b);
    }
    
    // 检查连通分量数
    int roots = 0;
    for (int i = 1; i <= n; i++) {
        if (parent[i] == i) {
            roots++;
        }
    }
    
    return roots == 1;  // 只有一个连通分量
}

3. 最小生成树与Kruskal算法

3.1 基本概念

生成树：包含图中所有顶点的连通无环子图
最小生成树：所有生成树中边权值和最小的那个
MST性质：至少存在一棵最小生成树包含当前最短边

3.2 Kruskal算法步骤

将所有边按权值从小到大排序
初始化并查集，每个顶点自成一个集合
按顺序选择每条边，如果边的两个顶点不在同一集合，则选择该边并合并集合
重复步骤3直到选择n-1条边（n为顶点数）

3.3 Kruskal算法实现

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

const int MAXM = 10005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

Edge edges[MAXM];
int parent[MAXM];

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

void merge(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

int kruskal(int n, int m) {
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 按边权排序
    sort(edges, edges + m);
    
    int totalWeight = 0;
    int edgeCount = 0;
    
    for (int i = 0; i < m && edgeCount < n - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        
        if (find(u) != find(v)) {
            merge(u, v);
            totalWeight += w;
            edgeCount++;
        }
    }
    
    if (edgeCount != n - 1) {
        return -1;  // 图不连通
    }
    
    return totalWeight;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < m; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
        }
        
        int result = kruskal(n, m);
        if (result == -1) {
            cout << "图不连通" << endl;
        } else {
            cout << "最小生成树权值和: " << result << endl;
        }
    }
    return 0;
}

3.4 算法正确性证明（MST性质）

命题：至少存在一棵最小生成树包含当前最短边。

反证法证明：

假设所有最小生成树都不包含最短边e
任取一棵最小生成树T，将e加入T中，必然形成环
环中必然存在一条边f≠e，且f的权值≥e（因为e是最短边）
用e替换f得到新生成树T'，其权值≤T的权值
这与"所有最小生成树都不包含e"矛盾，故假设错误

4. 实战技巧与优化

4.1 并查集优化

路径压缩

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

按秩合并（可选）

int rank[MAXN];  // 记录树的高度

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

void merge(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        // 按秩合并：矮树合并到高树下
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootA] = rootB;
            rank[rootB]++;
        }
    }
}

4.2 常见错误与注意事项

数组越界：注意顶点编号从0开始还是1开始
未初始化：每次使用前必须初始化并查集
浮点数比较：避免直接使用==比较浮点数
边数判断：Kruskal算法需要检查最终边数是否为n-1

4.3 代码规范建议

变量命名：使用有意义的变量名
函数封装：将并查集操作封装成函数
注释清晰：关键步骤添加注释
错误处理：考虑图不连通等边界情况

5. 学习建议

理解思想：掌握并查集"代表元素"的核心思想
多练习：从简单题目开始，逐步提高难度
调试技巧：使用小数据测试，理解每一步的变化
总结归纳：同类问题归纳总结，形成模板

通过系统学习并查集和最小生成树算法，你不仅能够解决经典的图论问题，还能培养抽象思维和算法设计能力。坚持练习，你会发现这些知识在竞赛和实际开发中都有广泛应用。

acm003 并查集与最小生成树算法详解