Cod sursa(job #1751691)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 1 septembrie 2016 19:13:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 50005
#define ALB 0
#define GRI 1
#define NEGRU 2
using namespace std;
ifstream cin("sortaret.in");
ofstream g("sortaret.out");
int n,timp,viz[NMAX],d[NMAX],f[NMAX];
stack<int> stiva;
vector<int> G[NMAX];
void citire(){
    int m;
    cin>>n>>m;
    int i,x,y;
    for(i=1;i<=m;i++){
        cin>>x>>y;
        G[x].push_back(y);
    }
}
void DFS(int x){
    d[x]=timp++;
    viz[x]=GRI;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
        if(viz[*it]==ALB)
            DFS(*it);
    viz[x]=NEGRU;
    f[x]=timp++;
    stiva.push(x);
}
void parcurg(){
    int i;
    for(i=1;i<=n;i++)
        if(viz[i]==ALB)
            DFS(i);
}
int main(){
    citire();
    parcurg();
    while(!stiva.empty()){
        g<<stiva.top()<<' ';
        stiva.pop();
    }
    return 0;
}