Count Unreachable Pairs of Nodes in an Undirected Graph Problem

Problem

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

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

Examples

Example 1:

1
2
3
4
5

Input:
n = 3, edges = [[0,1],[0,2],[1,2]]
Output:
 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

1
2
3
4
5
6

Input:
n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output:
 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].

Therefore, we return 14.

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.

Solution

Method 1 – Connected Components (DFS/Union-Find) (1)

Intuition

The key idea is that nodes in the same connected component can reach each other, but nodes in different components cannot. So, for each component, count its size, and the number of unreachable pairs is the sum over all pairs of nodes in different components.

Approach

  1. Build the graph from the edge list.
  2. Use DFS or Union-Find to find all connected components and their sizes.
  3. For each component of size s, the number of unreachable pairs contributed is s * (total_nodes_remaining - s).
  4. Accumulate the answer as you process each component.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        vector<bool> vis(n);
        function<int(int)> dfs = [&](int u) {
            vis[u] = true;
            int cnt = 1;
            for (int v : g[u]) if (!vis[v]) cnt += dfs(v);
            return cnt;
        };
        long long ans = 0, rem = n;
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                int sz = dfs(i);
                ans += (long long)sz * (rem - sz);
                rem -= sz;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func countPairs(n int, edges [][]int) int64 {
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    vis := make([]bool, n)
    var dfs func(int) int
    dfs = func(u int) int {
        vis[u] = true
        cnt := 1
        for _, v := range g[u] {
            if !vis[v] {
                cnt += dfs(v)
            }
        }
        return cnt
    }
    var ans int64
    rem := n
    for i := 0; i < n; i++ {
        if !vis[i] {
            sz := dfs(i)
            ans += int64(sz) * int64(rem-sz)
            rem -= sz
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public long countPairs(int n, int[][] edges) {
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        boolean[] vis = new boolean[n];
        long ans = 0, rem = n;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                int sz = dfs(i, g, vis);
                ans += (long)sz * (rem - sz);
                rem -= sz;
            }
        }
        return ans;
    }
    private int dfs(int u, List<Integer>[] g, boolean[] vis) {
        vis[u] = true;
        int cnt = 1;
        for (int v : g[u]) if (!vis[v]) cnt += dfs(v, g, vis);
        return cnt;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun countPairs(n: Int, edges: Array<IntArray>): Long {
        val g = Array(n) { mutableListOf<Int>() }
        for (e in edges) {
            g[e[0]].add(e[1])
            g[e[1]].add(e[0])
        }
        val vis = BooleanArray(n)
        var ans = 0L
        var rem = n
        fun dfs(u: Int): Int {
            vis[u] = true
            var cnt = 1
            for (v in g[u]) if (!vis[v]) cnt += dfs(v)
            return cnt
        }
        for (i in 0 until n) {
            if (!vis[i]) {
                val sz = dfs(i)
                ans += sz.toLong() * (rem - sz)
                rem -= sz
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def countPairs(self, n: int, edges: list[list[int]]) -> int:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        vis = [False] * n
        def dfs(u: int) -> int:
            vis[u] = True
            cnt = 1
            for v in g[u]:
                if not vis[v]:
                    cnt += dfs(v)
            return cnt
        ans = 0
        rem = n
        for i in range(n):
            if not vis[i]:
                sz = dfs(i)
                ans += sz * (rem - sz)
                rem -= sz
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push(e[1] as usize);
            g[e[1] as usize].push(e[0] as usize);
        }
        let mut vis = vec![false; n];
        fn dfs(u: usize, g: &Vec<Vec<usize>>, vis: &mut Vec<bool>) -> i64 {
            vis[u] = true;
            let mut cnt = 1;
            for &v in &g[u] {
                if !vis[v] {
                    cnt += dfs(v, g, vis);
                }
            }
            cnt
        }
        let mut ans = 0i64;
        let mut rem = n as i64;
        for i in 0..n {
            if !vis[i] {
                let sz = dfs(i, &g, &mut vis);
                ans += sz * (rem - sz);
                rem -= sz;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    countPairs(n: number, edges: number[][]): number {
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        const vis = Array(n).fill(false);
        let ans = 0, rem = n;
        const dfs = (u: number): number => {
            vis[u] = true;
            let cnt = 1;
            for (const v of g[u]) if (!vis[v]) cnt += dfs(v);
            return cnt;
        };
        for (let i = 0; i < n; i++) {
            if (!vis[i]) {
                const sz = dfs(i);
                ans += sz * (rem - sz);
                rem -= sz;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of nodes and m is the number of edges; each node and edge is visited once.
  • 🧺 Space complexity: O(n + m), for the adjacency list and visited array.