连通性问题
6432. 统计完全连通分量的数量 - 力扣（LeetCode）
使用 DFS 来遍历各个连通块, 在遍历的过程中记录当前连通的中点的数目 node_cnt 和边数 edge_cnt, 在记录边数的时候统计了两遍, 而且不存在重边,所以当 edge_cnt==node_cnt*(node_cnt-1) 时说明当前连通块中的点两两之间都有边, 即为一个连通分量
class Solution { public: int countCompleteComponents(int n, vector<vector<int>>& edges) { vector<vector<int>> g(n, vector<int>(n)); vector<bool> st(n); // 稠密图使用邻接矩阵来存 for(auto edge:edges){ int a=edge[0], b=edge[1]; g[a][b]=1; g[b][a]=1; } int edge_cnt=0; int node_cnt=0; // dfs的过程中记录点数和边数 function<void(int)> dfs=[&](int u){ st[u]=true; node_cnt++; for(int i=0;i<n;i++){ if(g[u][i]){ if(!st[i]) dfs(i); edge_cnt++; } } }; int res=0; for(int i=0;i<n;i++){ if(!st[i]){ // 找个一个新的连通块 edge_cnt=0, node_cnt=0; dfs(i); if(edge_cnt==node_cnt*(node_cnt-1)) res++; } } return res; } };
