Union-Find

GCD, primality tests, the sieve of Eratosthenes / linear sieve / smallest prime factor (SPF), connecting numbers by prime factors with Union-Find, and splitting an array by the last occurrence of prime factors

Connected components, grid flood fill, multi-source BFS, state-space BFS, shortest cycles, and recursion depth in DFS

LeetCode 827 note: label every island and record its size, then for each 0 add the sizes of the distinct neighboring islands plus 1

LeetCode 305 note: each new land cell adds an island, then merges with neighboring land, subtracting 1 per successful merge; skip repeated positions

LeetCode 1998 note: numbers in one component can be permuted freely; union each number with its prime factors via SPF, and the array sorts iff each position’s old and new values share a group

LeetCode 1627 note: no pairwise GCDs; for each z > threshold, connect all multiples of z, O(n log n) unions in total

LeetCode 323 note: count components with DFS or Union-Find; Union-Find without path compression is much slower

LeetCode 3873 note: merge points sharing an x or y into components; a new point joins at most two of them, so the answer is the two largest plus 1

LeetCode 2421 note: add nodes in increasing value order and count same-value nodes per Union-Find group

LeetCode 2382 note: work backward so removals become additions; the Union-Find root stores the segment sum, and the maximum only grows

LeetCode 3910 note: n is tiny, so enumerate subsets with a bitmask, check the even sum first, then check that the induced subgraph is connected

LeetCode note for Find if Path Exists in Graph, rebuilt from the original learning note