Cod sursa(job #372541)

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

vector <int> a[DIM];
int n, m, t, v[DIM], ord[DIM];

void DFS(int q)
{

    v[q] = 1;
    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)
        a[i].pb(0);

    int x, y;
    for (int i = 1; i <= m; ++i)
    {
        fscanf(f, "%d%d", &x, &y);
        a[x].pb(y);
        ++a[x][0];
    }
    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;
}