← 返回 google 的题目列表Reconstruct the BFS Path Before Reaching a Target
类型：online_judge
Given an unweighted directed graph, a source node start, and a target node target, use BFS (Breadth-First Search) to find a shortest path from start to target.
Return all nodes on that path before reaching target. In other words, return the path from start through the predecessor of target, excluding target itself.
If start == target, output an empty path.
If target is unreachable, output -1.
Nodes are numbered from 0 to n - 1.
Edge input order determines BFS neighbor visitation order. If multiple shortest paths exist, return the first one discovered by BFS.
Input Format
n m
u1 v1
u2 v2
...
um vm
start target
Each u v line represents a directed edge from u to v.
Output Format
If a path exists, print node IDs from start through the predecessor of target, separated by spaces.
If start == target, print an empty line.
If target is unreachable, print -1.
Example
Input:
5 5
0 1
0 2
1 3
2 3
3 4
0 4
Output:
0 1 3
The first shortest path found by BFS is 0 -> 1 -> 3 -> 4; therefore, the nodes before reaching 4 are 0 1 3.
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 5 * 10^5
0 <= start, target < n
The graph may contain cycles and duplicate edges.
Example
Input
5 5
0 1
0 2
1 3
2 3
3 4
0 4
Output
0 1 3