Cod sursa(job #1447413)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 iunie 2015 12:30:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#define DIM 50010
using namespace std;

int F[DIM], Viz[DIM], S[DIM], K, N, M, X, Y;
vector <int> V[DIM];

void DFS(int nod){
    Viz[nod] = 1;
    for(int i = 0; i < V[nod].size(); i ++){
        int vecin = V[nod][i];
        if(Viz[vecin] == 0)
            DFS(vecin);
    }
    S[++K] = nod;
    return;
}

int main(){

    ifstream fin ("sortaret.in" );
    ofstream fout("sortaret.out");

    fin >> N >> M;
    for(int i = 1; i <= M; i ++){
        fin >> X >> Y;
        V[X].push_back(Y);
        F[Y] ++;
    }

    for(int i = 1; i <= N; i ++)
        if(F[i] == 0)
            DFS(i);

    for(int i = N; i >= 1; i --)
        fout << S[i] << " ";

    return 0;
}