「NOIP模拟赛」Graph

2014年10月30日1,0800

「题目描述」

给出 N 个点,M 条边的有向图,对于每个点 v,求 A(v) 表示从点 v 出发,能到达的编号最大的点。

「输入格式」

第 1 行,2 个整数 N,M。 接下来 M 行,每行 2 个整数 Ui,Vi,表示边 ⟨Ui,Vi⟩。点用 1,2,…,N 编号。

「输出格式」

N 个整数 A(1),A(2),…,A(N)。

「样例输入」

4 3

1 2

2 4

4 3

「样例输出」

4 4 3 4

「数据范围」

对于 60% 的数据,1 ≤ N,K ≤ 10^3

对于 100% 的数据,1 ≤ N,M ≤ 10^5。

题解

反建图 bfs

 

说点什么

提醒
avatar