Cod sursa(job #504774)

Utilizator mraresMardare Rares mrares Data 28 noiembrie 2010 17:24:53
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#define nmax 50000
#define mmax 100000

using namespace std;

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

struct lista
{
    int inf;
    lista *nod;
} *G[nmax];

int uz[nmax], grad[nmax], c[nmax];
int n, m, st, dr, x, y;

int main()
{
    int i;
    fscanf(fin, "%d%d", &n, &m);
    for(i=1;i<=n;++i)
    {
        fscanf(fin, "%d%d", &x, &y);
        ++grad[y];
    }
    for(i=1;i<=m;++i)
        if(!grad[i])
        {
            c[++dr]=i;
            uz[i]=1;
        }
    st=1;
    lista *p;
    for(; st<=dr; ++st)
    {
        //fprintf(fout, "%d ", c[st]);
        for(p=G[c[st]]; p; p=p->nod)
        {
            --grad[p->inf];
            if(!grad[p->inf] && !uz[p->inf])
            {
                c[++dr] = p->inf;
                uz[p->inf] = 1;
            }
        }
    }
    for(i=1;i<=n;++i)
        fprintf(fout, "%d ", c[i]);
    return 0;
}