luogu#P3916. 图的遍历

    ID: 7944 远端评测题 1000ms 125MiB 尝试: 33 已通过: 13 难度: 3 上传者: 标签>图的建立建图图论强连通分量缩点搜索邻接表

图的遍历

题目描述

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

输入格式

1122 个整数 N,MN,M,表示点数和边数。

接下来 MM 行,每行 22 个整数 Ui,ViU_i,V_i,表示边 (Ui,Vi)(U_i,V_i)。点用 1,2,,N1,2,\dots,N 编号。

输出格式

一行 NN 个整数 A(1),A(2),,A(N)A(1),A(2),\dots,A(N)

4 3
1 2
2 4
4 3
4 4 3 4

提示

  • 对于 60%60\% 的数据,1N,M1031 \leq N,M \leq 10^3
  • 对于 100%100\% 的数据,1N,M1051 \leq N,M \leq 10^5