Start with n elements, apply the given union operations, then answer connectivity
queries: for each query a,b, is a in the same group as b?
connectivity(n, unions, queries)
Input format: n | unions | queries, both as a,b pairs. Output the booleans
space-separated.
n=5, unions (0,1)(1,2), queries (0,2)(0,3) // → [true, false]
Two phases glued together: build a picture of which elements end up grouped after all unions, then answer "are these two in the same group?" for each query. Union-find is designed for exactly this split — cheap merges, cheap membership questions.
A naive approach builds an explicit graph and runs BFS/DFS per query to check connectivity — repeating work, since every query re-explores potentially large chunks of the graph. Union-find maintains a compressed "which root does each element belong to" incrementally. Once built, "are a and b connected" reduces to: do they share a root?
The invariant: two elements share a group exactly when following their parent pointers leads to the same root. Every merge preserves this by construction, and path compression never changes which root a chain leads to — only speeds up future lookups. So root equality accurately reflects "connected, directly or transitively, by the unions." Processing all unions first, then all queries, is correct and efficient: each find costs near-constant time thanks to path compression, so the whole process runs in close to linear time.
def connectivity(n, unions, queries):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in unions:
parent[find(a)] = find(b)
return [find(a) == find(b) for a, b in queries]
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.