【LetMeFly】2685.统计完全连通分量的数量DFS求每个连通块的边点数力扣题目链接https://leetcode.cn/problems/count-the-number-of-complete-components/给你一个整数n。现有一个包含n个顶点的无向图顶点按从0到n - 1编号。给你一个二维整数数组edges其中edges[i] [ai, bi]表示顶点ai和bi之间存在一条无向边。返回图中完全连通分量的数量。如果在子图中任意两个顶点之间都存在路径并且子图中没有任何一个顶点与子图外部的顶点共享边则称其为连通分量。如果连通分量中每对节点之间都存在一条边则称其为完全连通分量。示例 1输入n 6, edges [[0,1],[0,2],[1,2],[3,4]]输出3解释如上图所示可以看到此图所有分量都是完全连通分量。示例 2输入n 6, edges [[0,1],[0,2],[1,2],[3,4],[3,5]]输出1解释包含节点 0、1 和 2 的分量是完全连通分量因为每对节点之间都存在一条边。 包含节点 3 、4 和 5 的分量不是完全连通分量因为节点 4 和 5 之间不存在边。 因此在图中完全连接分量的数量是 1 。提示1 n 500 edges.length n * (n - 1) / 2edges[i].length 20 ai, bi n - 1ai! bi不存在重复的边解题方法深度优先搜索DFS从0 00到n − 1 n-1n−1遍历每一个节点如果当前节点还没有被遍历过则说明又找到了一个新的联通块从这个节点开始DFS。DFS要遍历与这个节点相连的所有节点和所有边并求出共有多少个。如果边 点 × ( 点 − 1 ) 2 边\frac{点\times(点-1)}{2}边2点×(点−1)则说明这个连通分量是完全连通分量。注意实际代码实现过程中每条边可能被其相连的两个节点共计遍历两次时间复杂度O ( l e n ( e d g e s ) n ) O(len(edges)n)O(len(edges)n)时间复杂度是边数点数;空间复杂度O ( l e n ( e d g e s ) n ) O(len(edges)n)O(len(edges)n)边的空间复杂度来自图的邻接表点点空间复杂度来自DFS最大深度。AC代码C/* * LastEditTime: 2026-07-11 08:40:46 */typedefpairint,intpii;classSolution{private:vectorboolvisited;vectorvectorintgraph;piidfs(intfrom){visited[from]true;intedge0,node1;for(intto:graph[from]){edge;if(!visited[to]){auto[next_edge,next_node]dfs(to);edgenext_edge;nodenext_node;}}return{edge,node};}public:intcountCompleteComponents(intn,vectorvectorintedges){graph.resize(n);for(vectorintedge:edges){graph[edge[0]].push_back(edge[1]);graph[edge[1]].push_back(edge[0]);}visited.resize(n);intans0;for(inti0;in;i){if(!visited[i]){auto[edge,node]dfs(i);ansedgenode*(node-1);// no need to /2}}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
