【题目来源】
https://www.luogu.com.cn/problem/B3862
【题目描述】
给出 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)。
【数据范围】
对于 100% 的数据，1≤N,M≤10^3。
【输入样例】
4 3
1 2
2 4
4 3
【输出样例】
4 4 3 4
【算法分析】
● 本题的“链式前向星”实现，详见：https://blog.csdn.net/hnjzsyjyj/article/details/147341814
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5 + 5;
vector<int> g[N];
int mx[N]; //max node-number reached by node i.
int n,m;void dfs(int u,int v) {mx[v]=u;for(int x:g[v]) {if(mx[x]==0) dfs(u,x);}
}int main() {cin>>n>>m;for(int i=0; i<m; i++) {int x,y;cin>>x>>y;g[y].push_back(x); //y →x}for(int i=n; i>=1; i--) {if(mx[i]==0) dfs(i,i);}for(int i=1; i<=n; i++) {cout<<mx[i]<<" ";}return 0;
}/*
in:
4 3
1 2
2 4
4 3out:
4 4 3 4
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/147341814
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
https://blog.csdn.net/hnjzsyjyj/article/details/147326357
https://blog.csdn.net/hnjzsyjyj/article/details/147333181
https://www.acwing.com/solution/content/3999/