Cod sursa(job #728816)

Utilizator freakingVlad Eu freaking Data 28 martie 2012 23:44:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#define in "sortaret.in"
#define out "sortaret.out"
#include <cstdio>
#define nmax 50001
#include <vector>
using namespace std;


int q[nmax],deg[nmax];
vector <int> V[nmax];

int main()
{
    int i,x,y;
    int N,M,naux,maux;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    scanf("%d %d",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d %d",&x,&y);
        {
            V[x].push_back(y);
            ++deg[y];
        }
    }

    for(i=1;i<=N;i++)
    {
        if(!deg[i])
            q[++q[0]]=i;
    }
    int cr;
    vector <int> :: iterator it;
    for(i=1;i<=N;i++)
    {
        cr=q[i];
        for(it=V[cr].begin();it!=V[cr].end();it++)
        {
            --deg[*it];
            if(!deg[*it])
                q[++q[0]]=*it;
        }

    }

    for(i=1;i<=N;i++)
        printf("%d ",q[i]);
    return 0;
}