Cod sursa(job #1461114)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 14 iulie 2015 19:07:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
 
 
#define MAX 100000
 
using namespace std;
 
int N = 0, M = 0;
 
vector <int> sortat, c(MAX);
vector <int> top[MAX];
stack <int> st;
 
 
 
void exporare(int u){
    c[u] = 1;
 
    for(unsigned int i = 0; i < top[u].size();i++){
        int v = top[u][i];
        if(c[v] == 0) exporare(v);
        if(c[v] == 1){
            cout << "Eroare:ciclu!\n";
            return;
        }
    }
    c[u] = 2;
    st.push(u);
}
 
 
 
void DFS(){
    for(int i = 1; i <= N; i++){
        if(c[i] == 0)
            exporare(i);
    }
}
 
 
 
int main(){
 
    freopen("sortaret.in","rt",stdin);
    freopen("sortaret.out","wt",stdout);
 
    cin >> N >> M;
 
    int x, y;
 
    for(int i = 0; i < M; i++){
        cin >> x >> y;
        top[x].push_back(y);
    }
 
 
 
    DFS();
 
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
    cout << "\n";
}