Count Unreachable Pairs of Nodes in an Undirected Graph
Problem
You have an undirected graph with n nodes labeled 0 to n − 1 and a list of edges. Count the unordered pairs of distinct nodes that cannot reach each other through any path. Since n can reach 10⁵, the count can exceed a 32-bit integer.
n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]14def count_pairs(n, edges):
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:
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
ans, remaining = 0, n
for v in range(n):
if find(v) == v:
remaining -= size[v]
ans += size[v] * remaining
return ansfunction countPairs(n, edges) {
const parent = Array.from({ length: n }, (_, i) => i);
const size = new Array(n).fill(1);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (const [a, b] of edges) {
let ra = find(a), rb = find(b);
if (ra !== rb) {
if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
parent[rb] = ra;
size[ra] += size[rb];
}
}
let ans = 0, remaining = n;
for (let v = 0; v < n; v++) {
if (find(v) === v) {
remaining -= size[v];
ans += size[v] * remaining;
}
}
return ans;
}long countPairs(int n, int[][] edges) {
int[] parent = new int[n], size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
for (int[] e : edges) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra != rb) {
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
}
}
long ans = 0, remaining = n;
for (int v = 0; v < n; v++)
if (find(parent, v) == v) {
remaining -= size[v];
ans += (long) size[v] * remaining;
}
return ans;
}
int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}long long countPairs(int n, vector<vector<int>>& edges) {
vector<int> parent(n), sz(n, 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (auto& e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra != rb) {
if (sz[ra] < sz[rb]) swap(ra, rb);
parent[rb] = ra;
sz[ra] += sz[rb];
}
}
long long ans = 0, remaining = n;
for (int v = 0; v < n; v++)
if (find(v) == v) {
remaining -= sz[v];
ans += (long long) sz[v] * remaining;
}
return ans;
}Explanation
Two nodes can reach each other exactly when they sit in the same connected component, so a pair is unreachable exactly when its two nodes live in different components. The whole problem reduces to: find the size of every component, then count pairs that straddle two different components.
We find the components with union-find (disjoint set union). Every node starts as its own root with size 1. For each edge we find the roots of its endpoints; if they differ we merge the smaller component under the larger one (union by size) and add the sizes. find also performs path compression, pointing nodes at their grandparent as it walks up, which keeps the trees nearly flat.
The counting step uses a neat trick to avoid double counting. Keep remaining = n and visit each root once: subtract its component size s from remaining, then add s × remaining to the answer. Each component is paired only with the nodes that come after it, so every cross-component pair is counted exactly once. The same value also equals C(n,2) minus the sum of C(s,2) over components.
For the default example, the edges merge {0,2,4,5} into one component of size 4 and {1,6} into one of size 2, while node 3 stays alone. Counting: size 4 leaves remaining 3, adding 4 × 3 = 12; size 2 leaves remaining 1, adding 2 × 1 = 2; size 1 leaves remaining 0, adding 0. The answer is 14.
Each union or find runs in amortized inverse-Ackermann time α(n), which is effectively constant, so processing all edges plus the final scan over nodes is nearly linear. The answer can be as large as roughly n²/2 ≈ 5·10⁹, so Java and C++ accumulate it in a 64-bit integer.