Cod sursa(job #1910055)

Utilizator RaTonAndrei Raton RaTon Data 7 martie 2017 15:21:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int GR[50001];
vector <int> G[50001], F;
vector <int> :: iterator ig;
set <int> L; // lista nodurilor care au gradul interior 0(nu depind de alte noduri)
set <int> :: iterator il;
int N,M;
int main()
{
    int i, x, y;
    f >> N >> M;
    for( i = 1; i <= M; i++ ){
        f >> x >> y;
        G[x].push_back(y);
        GR[y]++;
    }
    for( i = 1; i <= N; i++ )
        if(GR[i] == 0){
           L.insert(i);
        }

    while(!L.empty()){
        il = L.begin();
        F.push_back(*il);
        L.erase(il);
        x = (*il);
        for(ig = G[x].begin(); ig < G[x].end(); ig++){
            y = (*ig);
            GR[y]--;
            if( GR[y] == 0 )
                L.insert(y);
        }
        G[x].clear();
    }

    for(ig = F.begin(); ig < F.end(); ig++)
        g << *ig << " ";
    /*for( i = 1; i <= N; i++ ){
        g << i << " ";
        for( ig = G[i].begin(); ig < G[i].end(); ig++)
            g << *(ig) << " ";
        g << endl;
    }*/

    return 0;
}