Cod sursa(job #1687879)

Utilizator savinvadim1312savin vadim savinvadim1312 Data 13 aprilie 2016 09:37:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <set>
#include <queue>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

set <int> G[50005];
set <int> :: iterator it;
queue <int> Q;
int Deg[50005];

int N,M;

void citire(){
    int a,b;
    f>>N>>M;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        if(G[a].find(b) == G[a].end()){
            G[a].insert(b);
            Deg[a]++;
        }
    }
}
void init_q(){
    for(int i=1;i<=N;i++){
        if(Deg[i]==0){
            Q.push(i);
        }
    }
}
void sortare(){
    while(!Q.empty()){
        g<<Q.front();
        it = G[Q.front()].begin();
        for( ; it != G[Q.front()].end(); it++){
            Deg[*it]--;
            if(Deg[*it] == 0){
                Q.push(*it);
            }
        }
        Q.pop();
    }
}

int main()
{
    citire();
    init_q();
    sortare();

    return 0;
}