CSES 1667 Message Route - Implementation

Here is the full solution for Message Route:

function messageRoute(n, adj):
    dist = [infinity] * (n + 1)
    parent = [0] * (n + 1)

    dist[1] = 0
    queue.push(1)

    while queue is not empty:
        u = queue.pop_front()
        for each v in adj[u]:
            if dist[v] == infinity:
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.push(v)

    if dist[n] == infinity:
        print "IMPOSSIBLE"
    else:
        path = []
        current = n
        while current != 0:
            path.append(current)
            current = parent[current]
        path.reverse()
        print path.length
        print path

This pattern appears in many BFS problems that ask you to report the actual shortest path.

This runs in $O(V + E)$ time and uses $O(V)$ space.