📊 统计完全连通分量的数量

📝 题目描述

​ 给你一个整数n。现有一个包含n个顶点的无向图，顶点按从0到n - 1编号。给你一个二维整数数组edges，其中 $edges[i]=[a_i,b_i]$ 表示顶点 $a_i$ 和 $b_i$ 之间存在一条无向边。

​ 返回图中的完全连通分量的数量。

​ 如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为连通分量。

​ 如果连通分量中每对节点之间都存在一条边，则称其为完全连通分量。

📋 代码模板

java

class Solution {
    public int countCompleteComponents(int n, int[][] edges) {

    }
}

typescript

function countCompleteComponents(n: number, edges: number[][]): number {

}

💡 提示

1. $1<=n<=50$
2. $0<=edges.length<=n\ast (n-1)/2$
3. $edges[i].length==2$
4. $0<=a_i<=n-1$
5. $0<=b_i<=n-1$
6. $a_i\ne b_i$
7. 不存在重复的边

🚀 示例

🖊️ 题解

DFS

本题的本质是在找连通分量。

java

class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            graph[x].add(y);
            graph[y].add(x);
        }
        boolean[] visited = new boolean[n];
        int completeComponents = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int[] result = new int[]{0, 0};
                dfs(graph, visited, result, i);
                int size = result[0], lines = result[1];
                if (size * (size - 1) == lines) {
                    completeComponents++;
                }
            }
        }
        return completeComponents;
    }

    private void dfs(List<Integer>[] graph, boolean[] visited, int[] result, int i) {
        if (visited[i]) {
            return;
        }
        visited[i] = true;
        result[0]++;
        result[1] += graph[i].size();
        for (int next : graph[i]) {
            if (!visited[next]) {
                dfs(graph, visited, result, next);
            }
        }
    }
}

typescript

function countCompleteComponents(n: number, edges: number[][]): number {
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const edge of edges) {
        const x = edge[0], y = edge[1];
        graph[x].push(y);
        graph[y].push(x);
    }
    const visited: boolean[] = Array(n).fill(false);
    let completeComponents = 0, size = 0, lines = 0;
    const dfs = (i: number): void => {
        if (visited[i]) {
            return;
        }
        visited[i] = true;
        size++;
        lines += graph[i].length;
        for (const next of graph[i]) {
            dfs(next);
        }
    }
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            size = 0, lines = 0;
            dfs(i);
            if (size * (size - 1) == lines) {
                completeComponents++;
            }
        }
    }
    return completeComponents;
}

BFS

如果没有

java

class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            graph[x].add(y);
            graph[y].add(x);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        int completeComponents = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.offer(i);
                visited[i] = true;
                int size = 0, lines = 0;
                while (!queue.isEmpty()) {
                    int originalI = queue.poll();
                    size++;
                    lines += graph[originalI].size();
                    for (int next : graph[originalI]) {
                        if (visited[next]){
                            continue;
                        }
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
                if (size * (size - 1) == lines) {
                    completeComponents++;
                }
            }
        }
        return completeComponents;
    }
}

typescript

function countCompleteComponents(n: number, edges: number[][]): number {
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const edge of edges) {
        const x = edge[0], y = edge[1];
        graph[x].push(y);
        graph[y].push(x);
    }
    const visited: boolean[] = Array(n).fill(false);
    const queue: number[] = [];
    let completeComponents = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            queue.push(i);
            visited[i] = true;
            let size = 0, lines = 0;
            while (queue.length > 0) {
                const originalI: number = queue.shift()!;
                size++;
                lines += graph[originalI].length;
                for (const next of graph[originalI]) {
                    if (visited[next]) {
                        continue;
                    }
                    queue.push(next);
                    visited[next] = true;
                }
            }
            if (size * (size - 1) == lines) {
                completeComponents++;
            }
        }
    }
    return completeComponents;
}

💭 复杂度分析