题目链接


又是一道神奇的题目,题目问从每个点能到达的编号最大的点,相当于一到多,这样可以建反向边,然后跑dfs。 每个点跑一遍dfs,从n到1循环。 代码:

    #include<bits/stdc++.h>
    using namespace std;

    int n,m,ans[100009];

    struct Edge{
        int to,nxt;
    }e[100009];
    int head[100009],tot;

    void add(int x,int y){
        e[++tot].to=y;
        e[tot].nxt=head[x];
        head[x]=tot;
    }

    void dfs(int x,int fa){
        if(ans[x]!=0) return;
        ans[x]=fa;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(ans[y]==0) dfs(y,fa);
        }
    }

    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            add(y,x);
        }
        for(int i=n;i>=1;i--){
            dfs(i,i);
        }
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        return 0;
    }
Last modification:March 14th, 2020 at 08:46 pm