Count Unreachable Pairs of Nodes in an Undirected Graph

Medium
467.

Count Unreachable Pairs of Nodes in an Undirected Graph

Count Unreachable Pairs of Nodes in an Undirected Graph is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon and Google interviews.

You are given n nodes labelled 0 through n - 1 and a list of undirected edges.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1

Input
n = 3, edges = [[0,1],[0,2],[1,2]]
Output
0

Example 2

Input
n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output
14

Example 3

Input
n = 4, edges = []
Output
6

Constraints

  • 1 <= n <= 60
  • 0 <= edges.length <= 90
  • There are no duplicate edges and no self-loops.
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countPairs = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Unreachable Pairs of Nodes in an Undirected Graph Solution

Count Unreachable Pairs of Nodes in an Undirected Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Unreachable Pairs of Nodes in an Undirected Graph is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon and Google interviews.

Problem statement

You are given n nodes labelled 0 through n - 1 and a list of undirected edges.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0

Example 2

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14

Example 3

Input: n = 4, edges = []
Output: 6

Constraints

  • 1 <= n <= 60
  • 0 <= edges.length <= 90
  • There are no duplicate edges and no self-loops.
  • The answer fits in a signed 32-bit integer.

Hints for Count Unreachable Pairs of Nodes in an Undirected Graph

  1. Hint 1

    Two nodes are reachable exactly when they sit in the same connected component.

  2. Hint 2

    So find the component sizes — union-find or a flood fill both work.

  3. Hint 3

    Every pair drawn from two different components is unreachable; accumulate size * (nodes counted so far) as you sweep the components.

How to solve Count Unreachable Pairs of Nodes in an Undirected Graph

Nodes are mutually reachable iff they share a component, so find component sizes and count cross-component pairs.

Approach

  1. Union-find with sizes.
  2. Sweep roots: add size · seenSoFar and then add size to seenSoFar.

Why it works

Every pair drawn from two different components is unreachable, and the running-sum sweep counts each such pair exactly once.

Complexity

  • Time — O((n + e) · α(n))
  • Space — O(n)

Pitfalls

  • The count can exceed 32 bits — use a wide integer.

Reference solution

Python

def countPairs(n: int, edges) -> int:
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            size[rb] += size[ra]
    unreachable = 0
    seen_so_far = 0
    for i in range(n):
        if find(i) != i:
            continue
        unreachable += size[i] * seen_so_far
        seen_so_far += size[i]
    return unreachable

Java

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

public static int countPairs(int n, int[][] edges) {
    int[] parent = new int[n];
    int[] size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int[] e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            size[b] += size[a];
        }
    }
    int unreachable = 0, seenSoFar = 0;
    for (int i = 0; i < n; i++) {
        if (findRoot(parent, i) != i) continue;
        unreachable += size[i] * seenSoFar;
        seenSoFar += size[i];
    }
    return unreachable;
}

C++

static int findRoot(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int countPairs(int n, vector<vector<int>>& edges) {
    vector<int> parent(n), size(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (const auto& e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            size[b] += size[a];
        }
    }
    int unreachable = 0, seenSoFar = 0;
    for (int i = 0; i < n; i++) {
        if (findRoot(parent, i) != i) continue;
        unreachable += size[i] * seenSoFar;
        seenSoFar += size[i];
    }
    return unreachable;
}

JavaScript

var countPairs = function(n, edges) {
    const parent = [], size = [];
    for (let i = 0; i < n; i++) {
        parent.push(i);
        size.push(1);
    }
    const find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (let i = 0; i < edges.length; i++) {
        const a = find(edges[i][0]);
        const b = find(edges[i][1]);
        if (a !== b) {
            parent[a] = b;
            size[b] += size[a];
        }
    }
    let unreachable = 0, seenSoFar = 0;
    for (let i = 0; i < n; i++) {
        if (find(i) !== i) continue;
        unreachable += size[i] * seenSoFar;
        seenSoFar += size[i];
    }
    return unreachable;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)