求最大连通分量代码
时间: 2023-06-22 16:22:18 浏览: 55
这里提供一个使用DFS(深度优先搜索)算法求解无向图最大连通分量的代码示例(C++实现):
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005; // 最大顶点数
vector<int> G[MAXN]; // 邻接表表示无向图
bool vis[MAXN]; // 记录顶点是否被访问过
// DFS遍历连通分量
void dfs(int u, int& cnt) {
vis[u] = true;
cnt++; // 连通分量顶点数+1
for (int v : G[u]) {
if (!vis[v]) {
dfs(v, cnt);
}
}
}
// 求最大连通分量
int maxComponent(int n) {
int ans = 0; // 最大连通分量的顶点数
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
int cnt = 0; // 当前连通分量的顶点数
dfs(i, cnt);
ans = max(ans, cnt);
}
}
return ans;
}
int main() {
int n, m;
cin >> n >> m; // 读入顶点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 读入一条边
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加两条边
}
cout << maxComponent(n) << endl; // 输出最大连通分量的顶点数
return 0;
}
```
该算法的时间复杂度为 $O(n+m)$,其中 $n$ 是顶点数,$m$ 是边数。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)