c++并查集求图中连通块数量

并查集（Disjoint-set data structure），又称为“路径压缩并联查找集”或 “链接-切割树”，是一种数据结构，常用于解决一系列元素之间的连接问题。它支持两个基本操作：

1. **合并集合（Union）**：将两个集合合并成一个。
2. **查询代表元（Find）**：确定某个元素属于哪个集合，并返回该集合的代表元。

在 C++ 中处理图的连通块数量问题时，我们通常采用并查集来统计图中连通分量的数量。这适用于有向图或无向图的情况，特别是当需要频繁更新边或者查询节点间的连通性时更为高效。

### 并查集实现步骤

#### 初始化
初始化并查集时，每个元素被视为独立的一个集合，其代表元为自己。

std::vector<int> parent(n); // n为元素总数
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 union_set(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

### 使用示例

假设有一个无向图，可以通过边列表表示：

std::vector<std::pair<int, int>> edges = {{1, 2}, {2, 3}, {4, 5}};

int main() {
    int n = 6; // 图中有6个顶点
    std::vector<bool> visited(n, false); // 记录已访问过的顶点
    int connectedComponents = 0;

    for (auto &edge : edges) {
        int u = edge.first - 1;
        int v = edge.second - 1;
        
        if (find(u) != find(v)) { // 如果两顶点不在同一个集合中，则它们之间有一条新边形成新的连通分量
            union_set(u, v);
            ++connectedComponents;
        }
    }

    printf("Number of connected components: %d\n", connectedComponents);

    return 0;
}

上述代码首先初始化了一个并查集，并遍历了所有的边。每遇到一条边，如果两个端点分别属于不同的集合，则说明找到了一个新的连通分量，因此计数加一。最后输出连通分量的数量。

### 相关问题:

1. 并查集的路径压缩如何工作？
2. 并查集是否适用于动态更新边的情况？
3. 并查集如何用于检测图是否存在环？