Cod sursa(job #198393)

Utilizator h_istvanHevele Istvan h_istvan Data 11 iulie 2008 08:38:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>  
#include <cstring>  
#include <vector>  
using namespace std;
#define MAXN 50001  

long n,m;
long deg[MAXN];
long q[MAXN];
vector<int> g[MAXN];

void read()
{
     long i,a,b;
     scanf("%ld %ld\n",&n,&m);
     for (i=1; i<=m; ++i)
     {
         scanf("%ld %ld\n",&a,&b);
         g[a].push_back(b);
         deg[b]++;
     }
}

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

void write()
{
     long i;
     for (i=1; i<=q[0]; ++i) printf("%ld ",q[i]);
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    
    read();
    solve();
    write();
    
    return 0;
}