Union Find: Components, Islands and Connectivity

Learning Outcome

Use DSU for dynamic connectivity, merged accounts, island additions, and offline edge-limit queries.

Pattern Recognition

Item	Detail
Core signal	The problem repeatedly connects items and asks whether they belong to the same group.
Use when	Edges are added, components merge, and you do not need full path reconstruction.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

DSU keeps only the component representative, which is enough for connectivity questions.

Exact Practice Question Names

Accounts Merge
Graph Valid Tree
Number of Islands II
Smallest String With Swaps
Checking Existence of Edge Length Limited Paths

Interview Approach

Initialize parent[i] = i.
Use path compression in find.
Union by rank or size.
For weighted offline queries, sort edges and queries by threshold before unioning.

Pseudocode

find(x):
  if parent[x] != x: parent[x] = find(parent[x])
  return parent[x]
union(a,b):
  ra = find(a); rb = find(b)
  if ra != rb: attach smaller to larger

Sample Dry Run

For accounts merge, every shared email unions two account indices. After all unions, each root collects its sorted emails.

Edge Cases

Duplicate union
Grid cell already activated
Owner name should not be part of DSU key
Queries with strict less-than edge limit

Common Mistakes

No path compression
Unioning names instead of emails/accounts
Forgetting 2D to 1D id conversion

Complexity

Item	Detail
Expected time	Almost O(alpha(n)) per operation after sorting if needed.
Expected space	O(n).

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.