2685.统计完全连通分量的数量：DFS求每个连通块的边点数

【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 <= 50
• 0 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 不存在重复的边

解题方法：深度优先搜索DFS

从$0$到$n-1$遍历每一个节点，如果当前节点还没有被遍历过，则说明又找到了一个新的联通块，从这个节点开始DFS。

DFS要遍历与这个节点相连的所有节点和所有边并求出共有多少个。如果$边=\frac{点\times(点-1)}{2}$，则说明这个连通分量是完全连通分量。（注意，实际代码实现过程中每条边可能被其相连的两个节点共计遍历两次）

• 时间复杂度$O(len(edges)+n)$，时间复杂度是边数+点数;
• 空间复杂度$O(len(edges)+n)$，边的空间复杂度来自图的邻接表，点点空间复杂度来自DFS最大深度。

AC代码

C++

/*
 * @LastEditTime: 2026-07-11 08:40:46
 */
typedef pair<int, int> pii;
class Solution {
private:
    vector<bool> visited;
    vector<vector<int>> graph;

    pii dfs(int from) {
        visited[from] = true;
        int edge = 0, node = 1;
        for (int to : graph[from]) {
            edge++;
            if (!visited[to]) {
                auto [next_edge, next_node] = dfs(to);
                edge += next_edge;
                node += next_node;
            }
        }
        return {edge, node};
    }
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        graph.resize(n);
        for (vector<int>& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        visited.resize(n);
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                auto [edge, node] = dfs(i);
                ans += edge == node * (node - 1);  // no need to /2
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源