Visa | Coding OA Questions and Solutions | SDE | Set - 11 | 2026 | Kumar K

Question

Q3. Virus Spread

 

There are "N" computers connected by "M" bidirectional network connections.

 

Some computers are initially infected.

 

The virus spreads through the network: if an infected computer is connected to another computer, that computer also becomes infected. This continues until no more computers can be infected.

 

Before the virus starts spreading, you may remove at most one computer.

 

Removing a computer also removes all network connections connected to it.

 

Your task is to determine the maximum number of computers that can be saved by optimally removing at most one computer.

 

A computer is considered saved if it is neither infected nor removed.

 

Example

 

N = 7

 

Edges:

0 1

1 2

2 3

3 4

4 5

5 6

 

Initially infected:

0 6

 

Without removing anything, all computers become infected.

 

If computer "3" is removed, the network becomes:

 

0 - 1 - 2

 

4 - 5 - 6

 

The virus cannot cross from one side to the other.

 

Determine the maximum number of computers that can be saved.

 

Constraints

 

- "1 <= N <= 2 * 10^5"

- "0 <= M <= 2 * 10^5"

- The graph may be disconnected.

- There may be multiple initially infected computers.

- You may remove zero or one computer.

 

Return the maximum number of saved computers.