C++11 和 Vector 实现无向图连通分量判断

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

vector<int> parent;

// 寻找根节点
int find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}

int main() {
    int N, M;
    cin >> N >> M;
    
    parent.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        parent[i] = i; // 初始化每个节点的父节点为自己
    }
    
    int vertex, edge;
    for (int i = 1; i <= M; i++) {
        cin >> vertex >> edge;
        int root_vertex = find(vertex);
        int root_edge = find(edge);
        if (root_vertex != root_edge) { // 如果两个顶点不属于同一个连通分量，则将它们合并
            parent[root_vertex] = root_edge;
        }
    }
    
    vector<int> count_vertex(N + 1, 0); // 记录每个连通分量中的顶点数
    vector<int> count_edge(N + 1, 0); // 记录每个连通分量中的边数
    
    for (int i = 1; i <= N; i++) {
        int root = find(i);
        count_vertex[root]++; // 统计每个连通分量中的顶点数
    }
    
    for (int i = 1; i <= M; i++) {
        int root = find(i);
        count_edge[root]++; // 统计每个连通分量中的边数
    }
    
    for (int i = 1; i <= N; i++) {
        if (count_vertex[i] != count_edge[i]) { // 如果存在某个连通分量的顶点数和边数不相等，则输出No
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

本代码使用 C++11 和 Vector 实现了一个判断无向图中每个连通分量是否满足顶点数和边数相等的算法。该算法利用并查集数据结构高效地进行连通分量判断。

算法步骤如下：

1. 初始化并查集：将每个节点的父节点设置为自身。
2. 建立边关系：将输入的边信息用于建立并查集中的关系，如果两个节点不属于同一个连通分量，则将它们合并。
3. 统计连通分量信息：遍历所有节点，统计每个连通分量中的顶点数和边数。
4. 判断连通分量是否满足条件：判断每个连通分量的顶点数和边数是否相等，如果不相等则输出 "No"，否则输出 "Yes"。

本代码使用了 C++11 的特性，例如自动类型推断和初始化列表。它还使用了 Vector 数据结构来存储并查集和统计信息。

通过使用并查集数据结构，本算法能够高效地判断每个连通分量是否满足条件，代码简洁易懂，易于理解和实现。