Pattern visualizer
Count Unreachable Pairs of Nodes in Undirected Graph
Two nodes are unreachable from each other exactly when they land in different connected components, so this never requires checking pairs directly. Find the size of every component with a BFS or DFS, then the count of REACHABLE pairs is just size*(size-1)/2 added up per component. Subtracting that sum from the total pairs among all n nodes, n*(n-1)/2, leaves exactly the unreachable pairs — one arithmetic pass after the components are known. Animated on: 7 nodes labeled 0..6 with undirected edges 0-2, 0-5, 2-4, 1-6, 5-4 — how many pairs of different nodes are unreachable from each other?.
Size every connected component, then subtract reachable pairs from the total
Undirected graph, n nodes
7 nodes and 5 undirected edges. A pair of nodes is unreachable exactly when they sit in different connected components, so the whole problem is: find the components, then count cross-component pairs.
1FUNCTION countPairs(n, edges):2 BUILD adjacency FROM edges3 FOR EACH node FROM 0 TO n - 14 IF node NOT visited5 size <- BFS(node, adjacency, visited)6 APPEND size TO sizes7 total <- n * (n - 1) / 28 reachable <- SUM(s * (s - 1) / 2 FOR s IN sizes)9 RETURN total - reachable
← / → step · space play · Home restart