← 返回 snowflake 的题目列表Wiki Hopper: Crawl All Reachable Pages
类型：online_judge
Wiki Hopper: Crawl All Reachable Pages
You are given a directed graph of web pages. Each page contains links to other pages. Given a starting page start, return every distinct page that can be reached from it by following zero or more links.
Pages are numbered from 0 to n - 1. The graph may contain cycles, self-loops, and multiple links to the same page. Each page must appear at most once.
Implement the traversal using breadth-first search (BFS), and output pages in their BFS discovery order.
Input Format
n m start
u1 v1
u2 v2
...
um vm
n: number of pages.
m: number of links.
start: starting page ID.
Each u v means page u has a link to page v.
Output Format
Print all pages reachable from start, separated by spaces, in BFS discovery order.
Example 1
Input:
5 5 0
0 1
0 2
1 3
2 3
3 4
Output:
0 1 2 3 4
Example 2
Input:
4 4 0
0 1
1 2
2 0
2 3
Output:
0 1 2 3
Constraints
1 <= n <= 200,000
0 <= m <= 500,000
0 <= start < n
0 <= u, v < n
Follow-up
If fetching a page's links is network I/O, how would you parallelize BFS with multiple threads while ensuring that no page is fetched more than once?
Example
Input
5 5 0
0 1
0 2
1 3
2 3
3 4
Output
0 1 2 3 4