Cod sursa(job #144435)

Utilizator DastasIonescu Vlad Dastas Data 27 februarie 2008 17:25:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>

const int maxn = 50001;

FILE *in = fopen("sortaret.in","r"), *out = fopen("sortaret.out","w");

struct graf
{
    int nod;
    graf *next;
};

int n, m;
int deg[maxn];
graf *a[maxn];

int p, u;
int c[maxn];

void add(int x, int y)
{
    graf *q = new graf;

    q->nod = y;
    q->next = a[x];
    a[x] = q;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    int x, y;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d", &x, &y);
        add(x, y);
        ++deg[y];
    }

    for ( int i = 1; i <= n; ++i )
        if ( !deg[i] )
            c[++u] = i;
}

void go()
{
    for ( p = 1; p <= u; ++p )
    {
        graf *q = a[ c[p] ];

        while ( q )
        {
            --deg[ q->nod ];
            if ( !deg[ q->nod ] )
                c[++u] = q->nod;

            q = q->next;
        }
    }

    for ( int i = 1; i <= n; ++i )
        fprintf(out, "%d ", c[i]);
    fprintf(out, "\n");
}

int main()
{
    read();
    go();


	return 0;
}