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.

Expected approach

• Disjoint Set Union: parent[] with PATH COMPRESSION on find and UNION BY RANK/SIZE — both optimizations together give O(α(n)) amortized (explain why one alone isn't enough for the hidden large tests). Maintain size[] at roots for group-size queries. Build unions from the edge list once, answer queries by root comparison. Mention when BFS/DFS is still right (edges streaming with offline queries → still DSU; path retrieval → traversal).