Dsa
Union Find
Medium
Network Friendships
You are managing a social media platform and need to track friendships among users. When two users become friends, they should belong to the same connected component. Implement a function that handles friendship operations and returns the size of the connected component each user belongs to after each operation.
Input format:
- The first line contains an integer N (1 ≤ N ≤ 1000), the number of users.
- The next line contains an integer Q (1 ≤ Q ≤ 10000), the number of friendship queries.
- Each of the next Q lines contains either 'friend a b' or 'size a', where 'friend a b' creates a friendship between users a and b, and 'size a' returns the size of the connected component that user a belongs to.
Output format:
- For each 'size a' query, output the size of the connected component that user a belongs to.
Example:
Input:
5
5
friend 1 2
size 1
friend 2 3
size 2
size 1
Output:
2
3
Key concepts
union_findsets
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