Editorial for Path Reconstruction

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

Because all edges have equal weight, BFS from $s$ ~s~ finds shortest paths by number of edges.

To break ties lexicographically, sort every adjacency list in increasing order before the BFS. The BFS queue then visits paths of the same length in lexicographic order. Therefore, the first time a vertex is reached, the stored parent gives the lexicographically smallest shortest path to that vertex.

After BFS, if $t$ ~t~ has no parent, it is unreachable. Otherwise, follow parent pointers backward from $t$ ~t~ to $s$ ~s~, reverse the sequence, and print it.

The time complexity is $O(n + m \log m)$ ~O(n + m \log m)~ due to sorting the adjacency lists, and the BFS itself is $O(n + m)$ ~O(n + m)~.

Implementation

from collections import deque
import sys


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

    n, m, s, t = data[:4]
    graph = [[] for _ in range(n + 1)]
    idx = 4
    for _ in range(m):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        graph[a].append(b)
        graph[b].append(a)

    for neighbors in graph:
        neighbors.sort()

    parent = [-1] * (n + 1)
    parent[s] = 0
    q = deque([s])

    while q:
        node = q.popleft()
        if node == t:
            break
        for neighbor in graph[node]:
            if parent[neighbor] == -1:
                parent[neighbor] = node
                q.append(neighbor)

    if parent[t] == -1:
        print(-1)
        return

    path = []
    node = t
    while node != 0:
        path.append(node)
        node = parent[node]
    path.reverse()

    print(len(path) - 1)
    print(*path)


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.