Archie

建反图，dfs

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int x,y;
struct e{
    int to;
    int ne;
} ed[100050];
int head[100005];
int p;
int vis[100005];
void add(int f,int to){
    p++;
    ed[p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
}
void dfs(int x,int f){
    if(vis[x]) return;
    vis[x]=f;
    for(int i=head[x];i;i=ed[i].ne){
        dfs(ed[i].to,f);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(y,x);
    }
    for(int i=n;i>=1;--i){
        dfs(i,i);   
    }
    for(int i=1;i<=n;++i){
        cout<<vis[i]<<" ";
    }
    return 0;
}