Cod sursa(job #970575)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 7 iulie 2013 13:24:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <vector>
#include <list>
#include <queue>
#include <iostream>
#include <fstream>
class Vertex
{
    int indegree,outdegree;
    std::list<int> adjacency;
public:
    Vertex();
    void add_o(int x);
    void add_i();
    void sub_i();
    int get_i();
    void print();
    friend void remover(std::vector<Vertex>&myV,int x,int &nV2,std::queue<int>&myQ);
};
int Vertex::get_i()
{
    return indegree;
}
Vertex::Vertex()
{
    indegree=0;
    outdegree=0;
}
void Vertex::add_o(int x)
{
    outdegree++;
    adjacency.push_back(x);
}
void Vertex::add_i()
{
    indegree++;
}
void Vertex::sub_i()
{
    indegree--;
}
void remover(std::vector<Vertex>&myV,int x,int &nV2,std::queue<int>&myQ)
{
    while(!myV[x].adjacency.empty())
    {
        int aux=myV[x].adjacency.front();
        myV[x].adjacency.pop_front();
        myV[aux].sub_i();
        nV2--;
        if(!myV[aux].get_i()) myQ.push(aux);
    }
}
int main(void)
{
    std::ifstream in("sortaret.in");
    std::list<int> myL;
    std::queue<int> myQ;
    std::vector<Vertex> myV;
    int nV1,nV2;
    in >> nV1;
    in >> nV2;
    for(int i(0);i<nV1;i++)
        myV.push_back(Vertex());
    for(int i(0);i<nV2;i++)
    {
        int x,y;
        in >> x;
        in >> y;
        x--; y--;
        myV[x].add_o(y);
        myV[y].add_i();
    }
    in.close();
    for(int i(0);i<nV1;i++)
        if(myV[i].get_i()==0) myQ.push(i);
    while(!myQ.empty())
    {
        int aux=myQ.front();
        myL.push_back(aux);
        myQ.pop();
        remover(myV,aux,nV2,myQ);
    }
    myV.erase(myV.begin(),myV.end());
    std::ofstream out("sortaret.out");
    while(!myL.empty())
    {
        out << myL.front() + 1 << ' ';
        myL.pop_front();
    }
    out << std::endl;
    out.close();
    return 0;
}