Cod sursa(job #2051101)

Utilizator DawlauAndrei Blahovici Dawlau Data 28 octombrie 2017 15:39:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<deque>
#include<list>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX=50005;
int in_degree[NMAX],Q[NMAX],n,m;
list<int>g[NMAX];
void read_data(){
    int from,to;
    fin>>n>>m;
    while(m--){
        fin>>from>>to;
        g[from].push_back(to);
        ++in_degree[to];
    }
}
void topological_sort(){
    int i,node;
    for(i=1;i<=n;++i)
        if(in_degree[i]==0)
            Q[++Q[0]]=i;
    list<int>::iterator it;
    for(i=1;i<=n;++i){
        node=Q[i];
        for(it=g[node].begin();it!=g[node].end();++it){
            --in_degree[*it];
            if(in_degree[*it]==0)
                Q[++Q[0]]=*it;
        }
    }
}
void print(){
    int i;
    for(i=1;i<=n;++i)
        fout<<Q[i]<<' ';
}
int main(){
    read_data();
    topological_sort();
    print();
}