冲刺阶段（第5个月）：图论基础 - 并查集精讲与连通性判断实战

在信息学奥赛CSP-J的备考过程中，图论基础是一个重要的部分，而并查集（Union-Find）数据结构则是解决图论中连通性问题的有力工具。本文将详细介绍并查集的原理，以及如何通过路径压缩和按秩合并两种优化方法提升效率，并附上连通分量检测的代码实现。

一、并查集的基本原理

并查集是一种用于处理不相交集合的合并及查询问题的数据结构。它主要支持两种操作：

1. 查找（Find）：确定元素属于哪一个子集。它可以用来确定两个元素是否属于同一子集。
2. 合并（Union）：将两个子集合并成同一个集合。

并查集的基本实现通常使用一个数组来表示集合，数组的索引代表元素，而数组的值代表该元素的父节点。初始时，每个元素的父节点都是它自己。

二、路径压缩优化

路径压缩是并查集的一种重要优化方法，其思想是在执行查找操作时，将查找路径上的所有节点直接连接到根节点，从而降低后续查找操作的时间复杂度。具体实现如下：

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

通过路径压缩，查找操作的时间复杂度接近O(1)。

三、按秩合并优化

按秩合并是另一种提升并查集效率的方法。其核心思想是在合并两个集合时，总是将高度较小的树合并到高度较大的树上，从而避免树的高度过度增长。具体实现需要维护一个秩数组，记录每个集合的高度（或大小）。

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

通过按秩合并，可以确保并查集操作的整体时间复杂度保持在较低水平。

四、连通分量检测

利用并查集，我们可以轻松地检测图中的连通分量数量。具体步骤如下：

1. 初始化并查集，每个节点作为一个独立的集合。
2. 遍历图中的每条边，对边的两个端点执行合并操作。
3. 遍历所有节点，统计根节点的数量，即为连通分量的数量。

五、代码实现

以下是一个完整的连通分量检测的代码实现：

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

vector<int> parent;
vector<int> rank;

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

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

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

int countComponents(int n, vector<vector<int>>& edges) {
    init(n);
    for (const auto& edge : edges) {
        unionSet(edge[0], edge[1]);
    }
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (parent[i] == i) {
            count++;
        }
    }
    return count;
}

int main() {
    int n = 5; // 节点数
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {3, 4}}; // 边集合
    cout << "连通分量数量: " << countComponents(n, edges) << endl; // 输出连通分量数量
    return 0;
}

通过本文的学习，相信大家对并查集有了更深入的理解，并能够在CSP-J备考中灵活运用。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！