Pagini recente » Cod sursa (job #124378) | Cod sursa (job #39305) | Cod sursa (job #2356497) | Cod sursa (job #465169) | Cod sursa (job #921751)
Cod sursa(job #921751)
#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;
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("sortare.out");
while(!myL.empty())
{
out << myL.front() << ' ';
myL.pop_front();
}
out.close();
return 0;
}