3471 - 图的遍历

题目描述

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

输入
  • 第 1 行:两个整数 N, M ,表示点数和边数。
  • 接下来 M 行:每行两个整数 U_i, V_i ,表示一条有向边 (U_i, V_i)
  • 点用 1, 2, \dots, N 编号。
输出

一行 N 个整数: A(1), A(2), \dots, A(N) ,表示从每个点出发能到达的最大编号点。

样例

输入

4 3
1 2
2 4
4 3

输出

4 4 3 4
说明

【数据范围】

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

解题思路(补充说明)

  • 对于每个点 v ,从它出发进行 DFS 或 BFS,记录能到达的所有点中的最大编号。
  • 可以优化:从后往前枚举点,利用记忆化或拓扑排序加速。
  • 注意:图中可能存在环,但只需关注可达性与最大编号。
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 14
通过人数 5
金币数量 3 枚
难度 基础


上一题 下一题