CSES 1667 Message Route - Path Reconstruction Idea

BFS computes distances, but it does not save the path by default. To reconstruct the path, track where each node came from. Use a parent array: int parent[N]. When you visit node $v$ from node $u$, set parent[v] = u. This creates a trail of breadcrumbs from the target back to the source. After BFS finishes, if you want the path to node $t$, start at $t$ and follow the parent pointers: t → parent[t] → parent[parent[t]] → ... until you reach the source. Reverse this sequence to get the path from source to target.