Skip to content

1054: 图的遍历 Hard

题目

题目描述

给定 $n$ 个点,$m$ 条边的有向图,对于每个点 $v$,求 $f(v)$ 表示从点 $v$ 出发能到达的编号最大的点(包括自己在内)。

输入格式

第一行有 $2$ 个整数 $n$, $m$。

接下来 $m$ 行,每行 $2$ 个整数 $u_i,v_i$, 表示 $u_i$ 到 $v_i$ 有一条边。

点用 $1,2,\cdots,n$ 编号。

输出格式

$n$ 个整数 $f(1),f(2),\cdots,f(n)$。

样例输入

输入样例1

text 5 5 1 3 4 1 2 5 5 3 2 1

输入样例2

text 5 0

样例输出

输出样例1

text 3 5 3 4 5

输出样例2

text 1 2 3 4 5

数据范围

$n,m\leq 10^5$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!