M2685.统计完全连通分量的数量

graph, 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
• 不存在重复的边

这是一个求解无向图中完全连通分量数量的问题。

解题思路

一个连通分量被称为完全连通分量，当且仅当该分量中的任意两个顶点之间都存在一条边。对于一个含有 $V$ 个顶点的连通分量，如果它是完全连通的，那么：

1. 该分量中的每个顶点的度数（相邻节点的数量）都必须是 $V-1$。
2. 因为连通分量之间没有边相连，所以分量中顶点的度数在原图中也应当恰好为 $V-1$。

基于这个性质，我们可以通过以下步骤来解决问题：

1. 构建邻接表：将给定的边集转化为邻接表，方便遍历和查询每个节点的度数。
2. 寻找连通分量：利用广度优先搜索（BFS）或深度优先搜索（DFS）遍历图。使用一个 visited 数组记录节点是否被访问过。对于每个未访问的节点，启动一次遍历，找出该节点所在的连通分量中的所有节点。
3. 判断是否为完全连通分量：对于找出的每个连通分量，设其节点总数为 $V$。遍历该分量中的每个节点，检查其在邻接表中的度数（即相邻节点的数量）是否等于 $V-1$。若该分量中的所有节点都满足此条件，则该分量是一个完全连通分量，计数器加 1。

Python 3 实现代码

from typing import List

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        # 构建邻接表
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            
        visited = [False] * n
        complete_components_count = 0
        
        # 遍历所有节点
        for i in range(n):
            if not visited[i]:
                # 存储当前连通分量中的所有节点
                component = []
                queue = [i]
                visited[i] = True
                
                # BFS 遍历获取当前连通分量
                head = 0
                while head < len(queue):
                    u = queue[head]
                    component.append(u)
                    for neighbor in adj[u]:
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            queue.append(neighbor)
                    head += 1
                
                # 检查当前连通分量是否为完全连通分量
                v_count = len(component)
                is_complete = True
                for node in component:
                    if len(adj[node]) != v_count - 1:
                        is_complete = False
                        break
                
                if is_complete:
                    complete_components_count += 1
                    
        return complete_components_count

复杂度分析

• 时间复杂度：$O(V+E)$，其中 $V=n$ 为顶点数，$E$ 为边数。构建邻接表需要 $O(E)$ 的时间；在 BFS 过程中，每个节点和每条边都只会被访问常数次，总时间复杂度为 $O(V+E)$。
• 空间复杂度：$O(V+E)$。邻接表需要 $O(V+E)$ 的空间，visited 数组以及 BFS 队列和连通分量记录需要 $O(V)$ 的空间。