Reachable Pair Check
Problem
A network has n nodes numbered 0 to n minus 1 and a list of two-way links between pairs of nodes. Given a source node and a target node, decide whether some chain of links leads from one to the other. A node always reaches itself.
Examples
Input: n = 3, links = [[0, 1], [1, 2], [2, 0]], source = 0, target = 2
Output: TrueInput: n = 6, links = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source = 0, target = 5
Output: False
Why: the links form two separate groups, {0, 1, 2} and {3, 4, 5}Input: n = 1, links = [], source = 0, target = 0
Output: True
Why: edge case, a node reaches itself without any linkHints
0 / 3
The exact route does not matter, only whether the two nodes end up in the same connected group.
Start with every node in a group of its own. Each link tells you that two groups are really one.
Give every node a parent pointer to itself. For each link, find the root of both ends by following parent pointers and point one root at the other. At the end, the answer is whether the source and the target have the same root.
Solution
Each link merges the groups of its two ends, so after processing every link the disjoint sets are exactly the connected groups, whatever order the links came in. Reachability is then one comparison of roots. Path halving, which points each visited node at its grandparent during a find, keeps the parent chains short without any extra bookkeeping. With m links, time is O((n + m) times the inverse Ackermann function), effectively linear, and space is O(n).
def reachable(n, links, source, target):
parent = list(range(n)) # every node starts alone
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for u, v in links:
parent[find(u)] = find(v) # a link merges two groups
return find(source) == find(target)
print(reachable(3, [[0, 1], [1, 2], [2, 0]], 0, 2)) # -> True
print(reachable(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5)) # -> False
print(reachable(1, [], 0, 0)) # -> TrueStuck on the idea rather than the code? Disjoint Sets Basics covers it.