Dsa
Union Find
Easy
Social Network Connections
You are given a list of friend connections in a social network. Each connection indicates two users that are friends. Your task is to calculate the number of distinct friend groups, where a group is defined as users that are all connected directly or indirectly through friendships.
Input format:
- The first line contains an integer `m` (1 <= m <= 500) representing the number of friendships.
- The next `m` lines each contain two lowercase letters representing the usernames (e.g., 'a b').
Output format:
- A single integer representing the number of distinct friend groups.
Example:
Input:
4
a b
b c
d e
d f
Output:
3
This indicates there are 3 distinct groups: {a, b, c}, {d, e, f}, and {d}.
Key concepts
union_findgraphsdisjoint_sets
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now