Dsa
Union Find
Easy
Social Network Components
You are tasked with analyzing a social network. Each user can follow multiple users, creating a directed graph. Given a list of user follow relationships, determine the number of strongly connected components (SCCs) in the network. Each user is represented by a unique ID (0-indexed). A strongly connected component is a subgraph where every user can reach every other user within that subgraph.
Input format:
- The first line contains an integer n, the number of users.
- The next line contains an integer m, the number of follow relationships.
- The subsequent m lines each contain two integers a and b, indicating that user a follows user b.
Output format:
- A single integer representing the number of strongly connected components.
Example:
Input:
5
5
0 1
1 2
2 0
1 3
3 4
Output:
2
Key concepts
union_findgraphconnected_components
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