题目选自洛谷P3916

反向建边 + dfs

按题目来每次考虑每个点可以到达点编号最大的点，不如考虑较大的点可以反向到达哪些点

循环从N到1，则每个点i能访问到的结点的A值都是i

每个点访问一次，这个A值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了

题目描述

给出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)。

输入输出样例

输入 1

4 3
1 2
2 4
4 3

输出 1

4 4 3 4

说明/提示

• 对于60% 的数据，1≤N.M≤10^3；

• 对于100% 的数据，1≤N,M≤10^5。

解题代码：

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> p[100001];
int ans[100001];
void dfs(int x,int v){
	ans[x] = v; //点xc保存最大值
	for(int i=0;i<(int)p[x].size();i++)
		if(ans[p[x][i]]==0) //没有走到过 就更新
			dfs(p[x][i],v);
}
int main(){
	int u,v;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		p[v].push_back(u);//反向建边
	}
	for(int i=n;i>=0;i--)
		if(ans[i] == 0) dfs(i,i); //对于每一次dfs的v值是一样的
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}