Cod sursa(job #2052918)

Utilizator CriogeniXBociat Daniel Tiberiu CriogeniX Data 31 octombrie 2017 10:38:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 50005;
int N, M;
bool used[NMAX];
vector <int> V[NMAX];
stack <int> sol;

void Read(){
    in >> N >> M;
    for(int i = 1; i <= M; ++i){
        int x, y;
        in >> x >> y;
        V[x].push_back(y);
    }
}

void DFS(int node){
    used[node] = true;
    for(int i = 0; i < (int)V[node].size(); ++i){
        int neighbour = V[node][i];
        if(!used[neighbour])
            DFS(neighbour);
    }
    sol.push(node);
}

void Solve(){
    for(int i = 1; i <= N; ++i){
        if(!used[i])
            DFS(i);
    }
}

void Print(){
    while(!sol.empty()){
        out << sol.top() << " ";
        sol.pop();
    }
    out << "\n";
}

int main(){
    Read();
    Solve();
    Print();
}