Cod sursa(job #1117072)

Utilizator denis_tdrdenis tdr denis_tdr Data 23 februarie 2014 00:14:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#define NMax 500001
using namespace std;

list<int> v[NMax];
list<int> L;
vector<bool> viz;
vector<int> extD;
int n, m, x, y;
void visit(int i){
    viz[i]=true;
    cout<<"viz:"<<i<<"\n";
    for(list<int>::iterator it=v[i].begin(); it!=v[i].end();it++)
        if(!viz[*it])
            visit(*it);
    L.push_front(i);
}
int main(){
    ifstream f("sortaret.in");
    f>>n>>m;
    extD=vector<int>(n+1, 0);
    while(f>>x>>y)
        v[x].push_back(y), extD[y]++;

    viz=vector<bool>(n+1, false);
    for(int i=1;i<=n;i++)
        if(extD[i]==0)visit(i);

    ofstream g("sortaret.out");
    for(list<int>::iterator it=L.begin(); it!=L.end();it++)
        g<<*it<<" ";
    return 0;
}