Social Connections

Problem Given social connections (friendship pairs) among users, answer connectivity queries — are X and Y connected (directly or transitively)? / how large is each social group? The input scale is designed so per-query BFS/DFS times out; Union-Find is the expected tool.

Input / Output

• Input: n users, edge list of friendships, then queries (connected(a,b) or component sizes).
• Output: per-query answers.

Constraints

• Users/edges/queries up to 10^5–10^6 — per-query O(V+E) traversal is too slow; near-O(1) amortized per operation required.

Example

• Friends: (1,2), (2,3), (4,5) → connected(1,3) = true; connected(1,4) = false; group sizes {1,2,3}=3, {4,5}=2.