描述 Description
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
输入格式 InputFormat
第 1 行，2 个整数 N,M。 接下来 M 行，每行 2 个整数 Ui,Vi，表示边 ⟨Ui,Vi⟩。点用 1,2,…,N 编号。
输出格式 OutputFormat
N 个整数 A(1),A(2),…,A(N)。
样例输入 SampleInput
4 3
1 2
2 4
4 3
样例输出 SampleOutput
4 4 3 4
代码 Code
按照方向边建图，从最大点开始枚举，每次 dfs 走没走过的点赋值，即每个点只会走一遍。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[200005];
int head[100005],ans[100005];
int cnt;
inline void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int s,int x)
{
int i,j,t;
if (ans[s]>0) return ;
ans[s]=x;
for (i=head[s];i;i=e[i].next) if (ans[e[i].to]==0)
{
dfs(e[i].to,x);
}
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
memset(ans,0,sizeof(ans));
cnt=0;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(y,x);
}
for (i=n;i>0;i--) dfs(i,i);
for (i=1;i<n;i++) printf("%d",ans[i]);
printf("%d\n",ans[n]);
return 0;
}