Editorial for Adjacency List Traversal

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

Build an adjacency list for the undirected graph. Sort every vertex's adjacency list in increasing order before starting the BFS.

During BFS, mark a vertex visited as soon as it is added to the queue. Because each adjacency list is sorted, the current vertex discovers its unvisited neighbors from smallest to largest, which matches the required tie-breaking rule.

Sorting all adjacency lists costs $O(m \log m)$ ~O(m \log m)~ in the worst case, and the BFS itself costs $O(n + m)$ ~O(n + m)~. The memory complexity is $O(n + m)$ ~O(n + m)~.

Solution (Python)

import sys
from collections import deque


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m, start = data[0], data[1], data[2]
    graph = [[] for _ in range(n + 1)]
    index = 3
    for _ in range(m):
        a = data[index]
        b = data[index + 1]
        index += 2
        graph[a].append(b)
        graph[b].append(a)

    for neighbors in graph:
        neighbors.sort()

    visited = [False] * (n + 1)
    visited[start] = True
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if not visited[nxt]:
                visited[nxt] = True
                queue.append(nxt)

    print(" ".join(map(str, order)))


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.