Count Unreachable Pairs of Nodes in an Undirected Graph
Medium · Graphs · about 15 minutes
Asked at Amazon, Google, Microsoft, Meta.
An undirected graph has n nodes and the edges edges. Count the pairs of distinct nodes with no path between them. In these tests the count fits in 32 bits.