Cod sursa(job #921751)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 21 martie 2013 12:38:36
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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;
		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;
}