Cod sursa(job #144728)

Utilizator floringh06Florin Ghesu floringh06 Data 27 februarie 2008 21:35:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define MAX_N 50005

int P[MAX_N]; // postordine
int viz[MAX_N];
int *A[MAX_N];

int M, N;
int v;

    void readdata ()
    {
         int x, y, i;
         scanf ("%d %d", &N, &M);
         for (i = 1; i <= N; ++i)
         {
             A[i] = (int *) realloc(A[i], sizeof (int));
             A[i][0] = 0;
         }
         for (i = 1; i <= M; ++i)
         {
             scanf ("%d %d", &x, &y);
             A[x][0]++;
             A[x] = (int *) realloc (A[x], (A[x][0] + 1)*sizeof (int));
             A[x][A[x][0]] = y;
         }
    }
    
    void DFS (int nod)
    {
         int i;
         viz[nod] = 1;
         for (i = 1; i <= A[nod][0]; ++i)
             if (!viz[A[nod][i]])
                DFS (A[nod][i]);
         P[++v] = nod;
    }
    
    void solve ()
    {
         int i;
         for (i = 1; i <= N; ++i)
             if (!viz[i])
                DFS (i);
         for (i = N; i; --i)
             printf ("%d ", P[i]);
    } 

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        readdata ();    
        solve ();
        
        return 0;
    }