Editorial for Adjacency List Traversal

Use this editorial only when stuck, and do not 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)$ in the worst case, and the BFS itself costs $O(n + m)$ . The memory complexity is $O(n + m)$ .

Solution (Python)

Code 1

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()

Comments0

No comments yet

Be the first to comment.

Editorial for Adjacency List Traversal

Approach

Solution (Python)

Comments0

New comment