Cod sursa(job #735274)

Utilizator visanrVisan Radu visanr Data 15 aprilie 2012 23:16:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;


#define nmax 50010
#define pb push_back


vector<long> nodes[nmax];
long grad[nmax],q[nmax],n,m,x,y;


void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             scanf("%ld %ld", &x,&y);
             nodes[x].push_back(y);
             grad[y]++;
     }
}

void solve()
{
     vector<long>::iterator it;
     for(int i=1;i<=n;i++) if(grad[i]==0) q[++q[0]]=i;
     for(int i=1;i<=n;i++)
     {
             long aux=q[i];
             for(it=nodes[aux].begin();it!=nodes[aux].end();++it)
             {
                       grad[*it]--;
                       if(grad[*it]==0) q[++q[0]]=*it;
             }
     }
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    //int i;
    read_input();
    solve();
    for(int i=1;i<=n;i++) printf("%ld ", q[i]);
    //scanf("%i", &i);
    return 0;
}