统计图的连通块的个数的两种方法

2019-11-06 08:43:40

字体：大中小

来源：转载

供稿：网友

@算法学习

两种方法

DFS遍历法并查集法

1. DFS遍历计算连通块

先上代码：

#include <stdio.h>#include <vector>using namespace std;const int maxn = 100010;vector<int> G[maxn]; // 邻接表存储图bool vis[maxn] = {false}; // 标记是否访问void dfs(int v){ vis[v] = true; for(int i = 0; i < G[v].size(); i++) { if(vis[G[v][i]] == false) { dfs(G[v][i]); // 如果该顶点未访问，深度遍历之 } }}int main(){ int n, a, b; scanf("%d", &n); for(int i = 1; i < n; i++) // n - 1条边 { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } int block = 0; // 枚举所有顶点 for(int i = 1; i <= n; i++) { if(vis[i] == false) { dfs(i); block++; } } PRintf("%d/n",block );}Input : 51 21 31 42 5Output:1Input: 51 31 42 53 4Output:2

注意到这里的dfs函数也没有人为控制递归边界；

dfs函数的目的就是为了标记单连通块中的所有结点，即令vis[v] = true;

在外围枚举所有顶点时，dfs一个顶点能把该块的所有顶点都“染色”为已经访问，通过控制语句，只有没访问过的才能进行dfs，那么一块只能有一个进来，所以可以进行计数。

2. 并查集法计算块数

#include <stdio.h>#include <vector>using namespace std;const int maxn = 100010;vector<int> G[maxn]; // 邻接表存储图bool isRoot[maxn] = {false}; // 标记是否访问int pre[maxn];int Find(int x){ int r = x; while(x != pre[x]) { x = pre[x]; } // 路径压缩:此时x已经是老大 int j; while(r != pre[r]) { j = r; r = pre[r]; pre[j] = x; } return x;}void Union(int a, int b){ int preA = Find(a); int preB = Find(b); if(preA != preB) { pre[preA] = preB; }}int calculateBlockNum(int n){ int block = 0; for(int i = 1; i <= n; i++) // 枚举所有顶点 { isRoot[Find(i)] = true;// 这样同样的数字只计算一次 } for(int i = 1; i <= n; i++) { block += isRoot[i]; //true当1用，false当0用 } return block;}void init(int n){ for(int i = 1; i <= n; i++) { pre[i] = i; }}int main(){ int n, a, b; scanf("%d", &n); init(n); // 很重要很重要！ for(int i = 1; i < n; i++) // n - 1条边 { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); Union(a,b); // 合并顶点a,b所在的集合 } int block = calculateBlockNum(n); printf("%d/n",block);}Input : 51 21 31 42 5Output:1Input: 51 31 42 53 4Output:2

这个也很好理解，用这个代码数会稍微多一些，但是并查集的通用性值得好好学习。

在输入边的两个顶点时就可以开始进行合并+路径压缩，这样统计pre数组中的元素有多少个不同值即可，为了统计，自然用到标记数组，这里不用统计每个块中的元素数目，所以用布尔型的数组即可。

上一篇：js文件被浏览器缓存的思考

下一篇：解决IDEA IntelliJ注册码冲突的问题