Cod sursa(job #504776)

Utilizator mraresMardare Rares mrares Data 28 noiembrie 2010 17:28:31
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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];

void add(int i, int j)
{
    lista *p;
    p = new lista;
    p->inf = j;
    p->nod = G[i];
    G[i] = p;
}

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<=m;++i)
    {
        fscanf(fin, "%d%d", &x, &y);
        add(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=1; 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;
}