❌ 统计无向图中无法互相到达点对数

📝 题目描述

​ 给你一个整数n，表示一张无向图中有n个节点，编号从0到n - 1。同时给你一个二维整数数组edges，其中 $edges[i]=[a_i,b_i]$ 表示节点 $a_i$ 和 $b_i$ 之间有一条无向边。

📋 代码模板

java

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

    }
}

typescript

function countPairs(n: number, edges: number[][]): number {
    
}

💡 提示

1. $1<=n<={10}^5$
2. $0<=edges.length<=2\ast {10}^5$
3. $edges[i].length==2$
4. $0<=a_i<n$
5. $0<=b_i<n$
6. $a_i\ne b_i$
7. 不会有重复边

🚀 示例

🖊️ 题解

DFS

可惜没有如果

java

class Solution {
    public long countPairs(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);
        }
        long pairs = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                long length = dfs(graph, visited, i);
                pairs += length * (n - length);
            }
        }
        return pairs / 2;
    }

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

typescript

function countPairs(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 pairs = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            const length = dfs(graph, visited, i);
            pairs += length * (n - length);
        }
    }
    return pairs / 2;
}

function dfs(graph: number[][], visited: boolean[], i: number): number {
    if (visited[i]) {
        return 0;
    }
    visited[i] = true;
    let length = 1;
    for (const next of graph[i]) {
        length += dfs(graph, visited, next);
    }
    return length;
}

BFS

java

class Solution {
    public long countPairs(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<>();
        long pairs = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.offer(i);
                visited[i] = true;
                long length = 1;
                while (!queue.isEmpty()) {
                    int originalI = queue.poll();
                    for (Integer next : graph[originalI]) {
                        if (!visited[next]) {
                            queue.offer(next);
                            visited[next] = true;
                            length++;
                        }
                    }
                }
                pairs += length * (n - length);
            }
        }
        return pairs / 2;
    }
}

typescript

function countPairs(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 pairs = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            queue.push(i);
            visited[i] = true;
            let length = 1;
            while (queue.length > 0) {
                const originalI: number = queue.shift()!;
                for (const next of graph[originalI]) {
                    if (!visited[next]) {
                        queue.push(next);
                        visited[next] = true;
                        length++;
                    }
                }
            }
            pairs += length * (n - length);
        }
    }
    return pairs / 2;
}

💭 复杂度分析