Disjoint Set Union-Find

Opening scenario

You're given n accounts and a stream of statements "account a and account b belong to the same person". After processing all statements, answer many queries "are x and y the same person?" — interleaved with more merge statements. Follow-up you should expect: Making A Large Island (LC 827) — in a nonempty square binary grid you may flip at most one 0 to 1; return the largest island size achievable. An island consists of 1-cells connected horizontally or vertically, and its size is its number of cells.

LC numbers identify LeetCode problems.

After a merge, which information must you retain so that later queries can tell whether two accounts belong to the same group?

Question progression

Q1 — Merges and "same group?" queries are interleaved. Why does graph traversal fall short?

Question: You could build a graph from the merge statements and BFS/DFS to answer each "same group?" query. Why does repeating a traversal become expensive when merges and queries are interleaved and numerous?