Cod sursa(job #1384029)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 10 martie 2015 20:13:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
const int M=100000;
const int N=50000;
class To{
    public:
        int v,nxt;
};
To g[M+1];
int start[N+1];
int res[N+1];
bool vis[N+1];
int n,m,p,nres;
void add_edge(int x,int y){
    g[++p].v=y;
    g[p].nxt=start[x];
    start[x]=p;
}
void dfs(int dad){
    vis[dad]=true;
    for(int i=start[dad];i;i=g[i].nxt){
        To son=g[i];
        if(!vis[son.v])
            dfs(son.v);
    }
    res[++nres]=dad;
}
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i);
    for(int i=n;i>=1;i--)
        printf("%d ",res[i]);
    return 0;
}