CSES 1667 Message Route - Path Reconstruction Algorithm

Run BFS and record parents as you go:

// During BFS, when visiting v from u:
parent[v] = u

// After BFS, reconstruct path from s to t:
path = []
current = t
while current != 0:
    path.append(current)
    current = parent[current]
path.reverse()

When you process node $u$ and visit neighbor $v$, set parent[v] = u before adding $v$ to the queue. After BFS completes, start at $t$ and backtrack through parents until you reach $s$. Reverse to get the path from $s$ to $t$.

If you never reached $t$ during BFS, parent[t] is still $0$, meaning no path exists.

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