P3916 

题目描述

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

输入输出格式

输入格式：

 

第1 行，2 个整数 N,MN,M 。

接下来 M 行，每行2个整数 U_i,V_i，表示边 (U_i,V_i)。点用 1,2,⋯,N 编号。

 

输出格式：

 

N 个整数 A(1),A(2),⋯,A(N) 。

 

输入输出样例

输入样例#1： 

4 31 22 44 3

输出样例#1： 

4 4 3 4

说明

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

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

　　今晚看偶然LXL dalao 在努力钻研着这个题，去和他研究了一会于是乎对这题产生了兴趣。

　　问了一圈人好像都是40,50,60分，还被个人嘲讽了（原因是我没做）。

　　独自静静回到电脑前，开始肆无忌惮的敲着代码，看着好像不是挺难。

　　貌似不太对哦，好像不是辣么简单。

　　要不先打个60分玩玩（额...60分好像不会写），要不....打正解？（.....）

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100011;int tot,head[maxn];int n,m,x,y;int f[maxn];struct ahah{    int nxt,to;}edge[maxn];void add(int x,int y)    // 灵光一闪，反向建边。 {    edge[++tot].nxt=head[y];edge[tot].to=x;head[y]=tot;}void dfs(int x,int d)    // dfs遍历能跑到哪？ {                        // d记录初始点(是有哪个点开始跑)     if(!f[x])f[x]=x;    for(int i=head[x];i;i=edge[i].nxt)    {        if(!f[edge[i].to])f[edge[i].to]=d,dfs(edge[i].to,d);    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);    for(int i=n;i>=1;i--)dfs(i,i);    // 要找跑到最大的点，所以反响跑最优。     for(int i=1;i<=n;i++)printf("%d ",f[i]);}