Cod sursa(job #198391)

Utilizator h_istvanHevele Istvan h_istvan Data 11 iulie 2008 08:20:52
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <vector>
#define MAXN 50001
using namespace std;

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[i].begin(); x!=g[i].end(); ++x)
         {
             deg[*x]--;
             if(!deg[*x]) q[++q[0]]=*x;
         }
     }
}

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

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