#K48547. Virus Spread in a Computer Network

    ID: 28444 Type: Default 1000ms 256MiB

Virus Spread in a Computer Network

Virus Spread in a Computer Network

You are given a network of N computers represented as an adjacency matrix \(A\) of size \(N \times N\). In this matrix, \(A[i][j] = 1\) indicates that computer i is directly connected to computer j, and \(A[i][j] = 0\) indicates no direct connection.

A virus starts spreading from a given computer virusStart and infects all computers that are directly or indirectly connected to it. Your task is to determine all the computers that become infected and then output their indices in ascending order (using 0-based indexing).

Note: The virus spreads recursively through all directly connected computers. Use depth-first search (DFS) or breadth-first search (BFS) to solve this problem.

inputFormat

The input is given via stdin in the following format:

  1. The first line contains an integer \(N\), the number of computers in the network.
  2. The next \(N\) lines each contain \(N\) space-separated integers (either 0 or 1) representing the rows of the adjacency matrix \(A\).
  3. The last line contains an integer virusStart, the index (0-based) of the computer where the virus starts.

It is guaranteed that \(1 \leq N \leq 1000\) and the matrix describes an undirected network.

outputFormat

Output a single line to stdout containing the sorted list of infected computer indices separated by a single space.

For example, if computers 0, 1, and 2 are infected, the output should be:

0 1 2
## sample
4
0 1 0 0
1 0 1 1
0 1 0 0
0 1 0 0
1
0 1 2 3