Medium

题目描述

给定一个整数 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
  • 没有重复的边

解题思路

这道题要求找到图中完全连通分量的数量。解题思路分为三个步骤：

  1. 构建图的邻接表表示：将边信息转化为便于遍历的图结构。

  2. 使用DFS/BFS找到所有连通分量：遍历所有未访问的节点，对每个未访问的节点进行深度优先搜索，找到它所属的连通分量。

  3. 判断每个连通分量是否完全：对于一个有 m 个节点的连通分量，如果它是完全图，那么它应该有 m*(m-1)/2 条边。我们可以在DFS过程中统计节点数和边数，然后验证这个条件。

核心观察：完全图的性质是每对顶点之间都有边。对于 m 个顶点的完全图，边数应该恰好是 C(m,2) = m*(m-1)/2。

算法流程：

  • 构建邻接表
  • 对每个未访问的节点进行DFS，统计该连通分量的节点数和边数
  • 检查边数是否等于 m*(m-1)/2
  • 统计满足条件的连通分量数量

推荐解法：使用DFS遍历，时间复杂度和空间复杂度都较优。

代码实现

class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        vector<bool> visited(n, false);
        int completeComponents = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int nodes = 0, edgeCount = 0;
                dfs(graph, visited, i, nodes, edgeCount);
                
                // 完全图的边数应该是 nodes * (nodes - 1) / 2
                if (edgeCount == nodes * (nodes - 1) / 2) {
                    completeComponents++;
                }
            }
        }
        
        return completeComponents;
    }
    
private:
    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node, int& nodes, int& edges) {
        visited[node] = true;
        nodes++;
        edges += graph[node].size();
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor, nodes, edges);
            }
        }
    }
};

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        visited = [False] * n
        complete_components = 0
        
        def dfs(node):
            visited[node] = True
            nodes = 1
            edge_count = len(graph[node])
            
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    sub_nodes, sub_edges = dfs(neighbor)
                    nodes += sub_nodes
                    edge_count += sub_edges
            
            return nodes, edge_count
        
        for i in range(n):
            if not visited[i]:
                nodes, edge_count = dfs(i)
                # 每条边被计算了两次，所以除以2
                if edge_count // 2 == nodes * (nodes - 1) // 2:
                    complete_components += 1
        
        return complete_components

public class Solution {
    public int CountCompleteComponents(int n, int[][] edges) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (int[] edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        bool[] visited = new bool[n];
        int completeComponents = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int nodes = 0, edgeCount = 0;
                Dfs(graph, visited, i, ref nodes, ref edgeCount);
                
                if (edgeCount / 2 == nodes * (nodes - 1) / 2) {
                    completeComponents++;
                }
            }
        }
        
        return completeComponents;
    }
    
    private void Dfs(List<int>[] graph, bool[] visited, int node, ref int nodes, ref int edgeCount) {
        visited[node] = true;
        nodes++;
        edgeCount += graph[node].Count;
        
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor]) {
                Dfs(graph, visited, neighbor, ref nodes, ref edgeCount);
            }
        }
    }
}

var countCompleteComponents = function(n, edges) {
    const adj = Array(n).fill().map(() => []);
    
    for (const [a, b] of edges) {
        adj[a].push(b);
        adj[b].push(a);
    }
    
    const visited = new Array(n).fill(false);
    let completeComponents = 0;
    
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            const component = [];
            dfs(i, adj, visited, component);
            
            if (isComplete(component, adj)) {
                completeComponents++;
            }
        }
    }
    
    return completeComponents;
};

function dfs(node, adj, visited, component) {
    visited[node] = true;
    component.push(node);
    
    for (const neighbor of adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited, component);
        }
    }
}

function isComplete(component, adj) {
    const size = component.length;
    
    for (const node of component) {
        if (adj[node].length !== size - 1) {
            return false;
        }
    }
    
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(V + E)V为顶点数，E为边数，需要遍历所有顶点和边
空间复杂度O(V + E)邻接表存储图需要O(V + E)空间，DFS递归栈最坏情况需要O(V)空间

相关题目