最短路

题目：最短路与图的遍历

题目描述

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

输入格式

第一行两个整数 \(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

数据范围

\(1 \leq N, M \leq 10^3\)

思路

方法1: 对每个点 DFS 的时间复杂度为 \(O(N(N+M))\)，在 \(N \leq 1000\) 时虽然可行（约 \(10^6\) 次操作）

方法2:

1. 反向图 + 从大到小遍历：将原图每条边反向，然后从编号最大的点开始，在反向图上做 BFS/DFS.
2. 每访问到一个新点，就将其答案设为当前起点（因为原图中这些点都能到达该起点）。

#include <bits/stdc++.h>
using namespace std;
vector<int> Edge[1002];
int n,m,Ans[1002],Q[1002];
int main() {cin>>n>>m;for (int i=1;i<=m;i++) {int x,y; cin>>x>>y;Edge[y].push_back(x);}for (int i=n;i>=1;i--)if (Ans[i]==0){Ans[i]=i;int f=0,r=1;Q[1]=i;while (f<r) {f++; int v=Q[f];for (auto e:Edge[v])if (Ans[e]==0) r++,Q[r]=e,Ans[e]=i;}}for (int i=1;i<=n;i++) cout<<Ans[i]<<" ";cout<<endl;return 0;
}