Dsa
Graphs Bfs
Medium
Network Outages
You are monitoring a network consisting of computers, each represented as a node. An outage can occur when certain connections between computers go down. You need to find all the connected components in the network after an outage. The connected components represent groups of computers that can still communicate with each other after some connections are removed. Write a program that determines the number of connected components in the network after specified outages.
Input format:
The first line contains integers n (number of computers) and m (number of connections).
The next m lines describe the connections, followed by an integer k (number of outages), and the next k lines describe the outages by specifying which connections (by index) are down.
Output format:
Output a single integer indicating the number of connected components remaining after the outages.
Example:
Input:
5 6
0 1
0 2
1 2
1 3
3 4
2 4
2
1
3
Output:
2
Key concepts
graphsbfsconnected-componentsnetwork
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