Cod sursa(job #1709165)

Utilizator pl4y0nHodorogea Alexandru pl4y0n Data 28 mai 2016 11:08:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;


int main()
{
    int NrVertex,NrEdges;

    vector<list<int>> edges;
    list<int> freeEdges;
    list<int> sortedVertex;
    vector<int> gradInterior;

    ifstream in("sortaret.in");

    in>>NrVertex>>NrEdges;

    edges.assign(NrVertex+1,list<int>());
    gradInterior.assign(NrVertex+1,0);

    for(int i=0; i<NrEdges; i++)
    {
        int x,y;
        in>>x>>y;
        edges[x].push_back(y);
        gradInterior[y]++;
    }

    in.close();

    for(int i=1; i<NrVertex+1; i++)
        if(gradInterior[i]==0)
            freeEdges.push_back(i);

    while(freeEdges.empty()==0)
    {
        int x,y;
        x = freeEdges.front();
        freeEdges.pop_front();
        sortedVertex.push_back(x);
        while(edges[x].empty()==0)
        {
            y=edges[x].front();
            edges[x].pop_front();
            gradInterior[y]--;
            if(gradInterior[y]==0)
                freeEdges.push_back(y);
        }
    }

    ofstream out("sortaret.out");

    for(list<int>::iterator i=sortedVertex.begin(); i!=sortedVertex.end(); i++)
        out<<*i<<" ";

    out.close();
    return 0;
}