Editorial for Matrix Reachability

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Use a breadth-first search starting from $s$ ~s~. Because the graph is given as an adjacency matrix, the neighbors of a vertex are found by scanning that vertex's entire row of the matrix.

Whenever row entry $j$ ~j~ is 1 and vertex $j$ ~j~ has not been visited yet, mark it visited and add it to the BFS queue. At the end, print all visited vertices in increasing order.

The BFS processes each reachable vertex once, and scanning one matrix row costs $O(n)$ ~O(n)~. The total time complexity is $O(n^2)$ ~O(n^2)~, and the memory complexity is $O(n^2)$ ~O(n^2)~ for the matrix.

Solution (Python)

import sys
from collections import deque


def main() -> None:
    data = sys.stdin.buffer.readline().split()
    n = int(data[0])
    start = int(data[1]) - 1

    matrix = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(n)]
    visited = [False] * n
    visited[start] = True
    queue = deque([start])

    while queue:
        node = queue.popleft()
        row = matrix[node]
        for nxt, has_edge in enumerate(row):
            if has_edge and not visited[nxt]:
                visited[nxt] = True
                queue.append(nxt)

    answer = [str(i + 1) for i, reachable in enumerate(visited) if reachable]
    print(" ".join(answer))


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.