DSA Tracker

Problem

Medium

Count Unreachable Pairs of Nodes in an Undirected Graph

A medium Graph interview guide. Task statement, worked examples, intuition, and step-by-step solutions.

Topic
Graph
Sheets
1
Core for
12 roles
PracticeWatch it step by step

The problem

A graph has n nodes numbered 0 to n - 1 and a list of undirected edges. Count the pairs of nodes that have no path between them at all.

Example 1

Input
n = 3, edges = [[0,1],[1,2]]
Output
0
Why
The chain connects everyone, so every pair can reach each other.

Example 2

Input
n = 6, edges = [[0,3],[1,4],[3,5]]
Output
11
Why
Groups of size 3, 2 and 1 give 3 + 1 reachable pairs out of 15 total: 11 pairs cannot reach each other.

Constraints

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5

How to think about it

Updated 2026-09-29

Total pairs of distinct nodes is `n * (n - 1) / 2`. Within any connected component of size s, all `s * (s - 1) / 2` pairs are reachable from each other. Subtracting the reachable pairs of every component from the total pairs yields the number of unreachable pairs in a single arithmetic pass.

Approaches, worst first

  1. Connected component sizes with combinatorial subtraction

    time O(V + E) · space O(V + E)

    Find sizes of all connected components using DFS or BFS. Total possible pairs is `n * (n - 1) / 2`. Subtract `size * (size - 1) / 2` for each component to find unreachable pairs. BigInt or 64-bit integers prevent overflow for n up to 10^5.

  2. Running suffix sum multiplicationWrite this one

    time O(V + E) · space O(V + E)

    Gather component sizes. Iterate through each component of size s, multiplying s by `remainingNodes - s` and adding to total, then decrementing remainingNodes by s.

Where people lose marks · 3
  • Integer overflow: with n = 10^5, the total number of pairs can exceed 5 * 10^9, overflowing standard 32-bit signed integers.
  • Isolated nodes with no edges are components of size 1 and must be included in the calculation.
  • When all nodes form a single connected component, the answer is 0 unreachable pairs.

Full solution

C++
#include <bits/stdc++.h>
using namespace std;

long long countPairs(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> visited(n, false);
    vector<long long> sizes;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            long long size = 0;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                size++;
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            sizes.push_back(size);
        }
    }
    long long total_pairs = (long long)n * (n - 1) / 2;
    long long intra_pairs = 0;
    for (long long s : sizes) {
        intra_pairs += s * (s - 1) / 2;
    }
    return total_pairs - intra_pairs;
}
Java
import java.util.*;

public class Main {
    static long countPairs(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        List<Long> sizes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                long size = 0;
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                visited[i] = true;
                while (!q.isEmpty()) {
                    int u = q.poll();
                    size++;
                    for (int v : adj.get(u)) {
                        if (!visited[v]) {
                            visited[v] = true;
                            q.offer(v);
                        }
                    }
                }
                sizes.add(size);
            }
        }
        long totalPairs = (long) n * (n - 1) / 2;
        long intraPairs = 0;
        for (long s : sizes) {
            intraPairs += s * (s - 1) / 2;
        }
        return totalPairs - intraPairs;
    }
}
Python
def count_pairs(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    sizes = []

    for i in range(n):
        if not visited[i]:
            size = 0
            q = [i]
            visited[i] = True
            for u in q:
                size += 1
                for v in adj[u]:
                    if not visited[v]:
                        visited[v] = True
                        q.append(v)
            sizes.append(size)

    total_pairs = n * (n - 1) // 2
    intra_pairs = sum(s * (s - 1) // 2 for s in sizes)
    return total_pairs - intra_pairs
JavaScript
function countPairs(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = Array(n).fill(1);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(x, y) {
    const rootX = find(x);
    const rootY = find(y);
    if (rootX !== rootY) {
      if (size[rootX] < size[rootY]) {
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
      } else {
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
      }
    }
  }

  for (const [u, v] of edges) {
    union(u, v);
  }

  let totalPairs = (BigInt(n) * BigInt(n - 1)) / 2n;
  let intraPairs = 0n;
  for (let i = 0; i < n; i++) {
    if (parent[i] === i) {
      const s = BigInt(size[i]);
      intraPairs += (s * (s - 1n)) / 2n;
    }
  }

  return Number(totalPairs - intraPairs);
}
Try it in the editor

The theory behind it

Graph — the ground this problem stands on. All Graph problems

What Graph is

A graph is a network of individual points, called vertices or nodes, connected by lines called edges. Think of a subway transit map, an electrical circuit, or a web of social friends. Unlike a tree, a graph has no designated top node and no parent-child hierarchy. Connections can run one-way or both ways, and paths can loop back on themselves to form closed cycles.

When to reach for it

Reach for graph algorithms when inputs describe relationships, networks, flights between cities, course prerequisites, or clone networks. Signals include finding the shortest route across unweighted connections, ordering tasks that depend on earlier tasks, counting isolated clusters, or checking whether a path contains an infinite loop. Whenever problems present pairs of related entities and ask for reachability, distances, or dependencies, graph representations apply.

How the pattern works

First convert edge lists into an adjacency list, mapping each node to an array of its neighbors. Choose your exploration strategy based on the goal: use a queue and breadth-first search to find the shortest path in unweighted networks, or use recursion and depth-first search to explore full paths and detect cycles. Because graphs can have loops, always track visited nodes in a set or boolean array. Add nodes to the visited set at the moment they enter the queue so they are never visited twice.

More Graph problems

Maximum Connected with One ChangeHardNumber of IslandsMediumClone GraphMediumCourse ScheduleMediumCourse Schedule IIMediumPacific Atlantic Water FlowMediumSurrounded RegionsMediumRotting OrangesMedium

Interactive Practice

PracticeWatch step-by-step visualizer

Target Roles

Core requirement for 12 roles:

SDE / Software EngineerBackend EngineerData EngineerGame DeveloperSecurity EngineerSite Reliability EngineerCloud EngineerComputer Vision EngineerRobotics EngineerCompiler / PL Engineer

Track in your role's order

Pick your target role and all 370 problems resequence to what that interview actually asks.

Start free

Problem set and role mapping as of .