Dsa
Union Find
Medium
Viral Outbreak Tracking
In a social network of N users, an infection is spreading. Some users are initially infected. When two users are connected by a link, if either user belongs to an infected component, the entire merged component becomes infected. Given the initial set of I infected users and M links formed over time, calculate the total number of infected users after all links are processed.
Example:
Input:
5 2 1
0
0 1
2 3
N=5, 1 initially infected (user 0).
Link 0-1: {0,1} becomes infected (2 users).
Link 2-3: {2,3} is healthy.
Final Infected: 2 (users 0 and 1).
Key concepts
union_finddynamic_growthgraph
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