Cod sursa(job #356130)

Utilizator floringh06Florin Ghesu floringh06 Data 13 octombrie 2009 17:01:58
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define MAX_N 50005
#define pb push_back
#define sz size

vector <int> G[MAX_N];

int V[MAX_N], P[MAX_N], S[MAX_N];
int N, M, cnt;

    void BFS (int nod)
    {
         int i;
         V[nod] = 1;
         for (i = 0; i <= S[nod]; ++i)
             if (!V[G[nod][i]]) BFS (G[nod][i]);
         P[++cnt] = nod;
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &N, &M);
        int i, x, y;
        
        for (i = 1; i <= M; ++i){
            scanf ("%d %d", &x, &y);
            G[x].pb (y);
        }
        
        for (i = 1; i <= N; ++i) S[i] = G[i].sz () - 1;
        
        BFS (1);
        
        for (i = cnt; i; --i) printf ("%d ", P[i]);
        
        return 0;
    }