Cod sursa(job #372544)

Utilizator cristiprgPrigoana Cristian cristiprg Data 10 decembrie 2009 19:09:57
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <vector>
using namespace std;
#define DIM 50005
#define pb push_back

struct nod
{
    int x;
    nod *next;
};
nod *list[DIM];


int n, m, t, v[DIM], ord[DIM];

void DFS(int q)
{

    v[q] = 1;
    nod *tt = list[q];
    while (tt != NULL)
    {
        if (!v[tt -> x])
            DFS(tt->x);

        tt = tt -> next;
    }

    /*
    for (int i =1 ; i <= a[q][0]; ++i)
        if (!v[a[q][i]])
            DFS(a[q][i]);
            */
    t++;
    ord[t] = q;
}

int main()
{
    FILE *f = fopen("sortaret.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
       list[i] = NULL;

    int x, y;

    for (int i = 1; i <= m; ++i)
    {
        nod *t;
        fscanf(f, "%d%d", &x, &y);
        t = new nod;
        t -> x = y;
        t -> next = NULL;
        list[x] = t;



    }
    for (int i = 1; i <= n; ++i)
        if (!v[i])
            DFS(i);

    fclose(f);
    f = fopen ("sortaret.out", "w");
    for (;t;--t)

        fprintf (f, "%d ", ord[t]);



    fclose(f);

    return 0;
}