Cod sursa(job #1785209)

Utilizator OleaginoasaCristina Oleaginoasa Data 20 octombrie 2016 22:43:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;

vector<int> G[50005];
int viz[50005];
stack<int> sol;

void sortareTopologica(int node){
    for(int i = 0; i < G[node].size(); ++i){
        int newNode = G[node][i];
        if(!viz[newNode]){
            sortareTopologica(newNode);
        }
    }
    
    viz[node] = 1;
    sol.push(node);
}

int main(){
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out","w", stdout);
    
    int N, M, u, v;
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; ++i){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    
    for(int i = 1; i <= N; ++i){
        if(!viz[i])
            sortareTopologica(i);
    }
    
    while(!sol.empty()){
        cout << sol.top() << " ";
        sol.pop();
    }
    
    return 0;
}