统计连通分量个数

求连通分量

 图的连通性

题目描述
给定一个n个节点m条边的无向图G，节点编号从1到n，保证图中没有重边和自环。

现在，你要统计G的连通分量数目C，以及每个连通分量的大小（节点数目）。

输入描述
第1行包含两个整数n,m (2≤n≤10 
4
 ,1≤m≤2×10 
5
 )，表示节点个数和边数。
接下来m行，每行包含两个整数u,v (1≤u,v≤n)，表示一条连接节点u和节点v的无向边。

输出描述
第一行，一个数字，表示图G的连通分量数目C。
第二行，包含C个整数，表示每个连通分量的大小，按照升序排列。

输入样例1
9 11
3 6
4 6
3 5
3 4
1 4
1 3
6 5
4 5
7 2
5 1
1 6
​
输出样例1
4
1 1 2 5
​
随机测试数据
子任务	平均占比	约束
子任务0	20%	n≤10,m≤20
子任务1	20%	n≤100,m≤200，且连通分量数目不超过2个
子任务2	60%	无约束
提示
在C++中，可以使用std::sort()和对整数数组按照升序或降序排列。

#include <algorithm>
#include <vector>

int main() {
  std::vector<int> arr;
  // ...
  std::sort(arr.begin(), arr.end()); // 升序排序
  std::sort(arr.begin(), arr.end(), greater<int>{}); // 降序排序
}
​

方案：

1. 初始化：创建一个数组或 visited 数组，记录每个节点是否被访问过。

2. 遍历每个顶点：对于每一个未访问的顶点，启动一个深度优先搜索（DFS）或者广度优先搜索（BFS），将该连通分量中的所有节点标记为已访问。

3. 计数连通分量：每当从一个未访问的顶点开始进行 DFS/BFS 时，说明找到一个新的连通分量，计数器加一。

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

vector<bool> visit;
vector<int> res;

class Graph{
public:
    int vertexNum;
    vector<vector<int>> adj;
    Graph(int n) : vertexNum(n), adj(n + 1){
    }
    void addEdge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};
void dfs(int startVertex, int& _size, Graph& graph){
    vector<int> nowList = graph.adj[startVertex];
    for(size_t i = 0; i < nowList.size(); i++){
        if(!visit[nowList[i]]){
            visit[nowList[i]] = 1;
            _size++;
            dfs(nowList[i], _size, graph);
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    Graph graph(n);
    visit.resize(n + 1);
    while(m--){
        int u, v;
        cin >> u >> v;
        graph.addEdge(u, v);
    }

    for(int i = 1; i <= n; i++){
        if(!visit[i]){
            visit[i] = 1;
            int _size = 1;
            dfs(i, _size, graph);
            res.push_back(_size);
        }
    }
    cout << res.size() << endl;
    sort(res.begin(), res.end());
    for(size_t i = 0; i < res.size(); i++){
        cout << res[i] << " ";
    }
    return 0;
}