Cod sursa(job #504766)

Utilizator mraresMardare Rares mrares Data 28 noiembrie 2010 16:54:17
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#define nmax 50000

using namespace std;

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

int uz[nmax], f[nmax];
int n, m, nr;

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;
}

void dfs(int k)
{
    lista *p;
    uz[k] = 1;
    for(p=G[k]; p; p=p->nod)
        if(!uz[p->inf])
            dfs(p->inf);
    f[++nr]=k;
}

int main()
{
    int i, j;
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d", &i, &j);
        add(i, j);
    }
    for(i=1; i<=n; ++i)
        if(!uz[i])
            dfs(i);
    for(i=n; i>=1; --i)
        fprintf(fout, "%d ", f[i]);
    return 0;
}