Cod sursa(job #1170229)

Utilizator stef93Stefan Gilca stef93 Data 12 aprilie 2014 22:50:43
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <list>

using namespace std;

list<int> * citesteGraf(ifstream &in, int &n)
{
	int x, y, i , m;
	list<int> *graf;

	in >> n >> m;

	graf = new list<int>[n + 1];

	for (i = 0; i < m; i++)
	{
		in >> x >> y;
		graf[x].push_front(y);
	}

	return graf;
}

list<int> sol;
bool *v;

void sortaret(int i , list<int> *graf)
{
	v[i] = true;

	for (list<int>::iterator it = graf[i].begin(); it != graf[i].end(); it++)
	{
		if (v[*it] == false)
		{
			sortaret(*it, graf);
		}
	}
	sol.push_front(i);
}
int main()
{
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");

	list<int> *graf;
	int n;

	graf = citesteGraf(in, n);
	v = new bool[n];
	for (int i = 1; i <= n; i++)
	{
		v[i] = false;
	}

	for (int i = 1; i <= n; i++)
	{
		if (v[i] == false)
		{
			sortaret(i, graf);
		}
	}

	for (list<int>::iterator it = sol.begin(); it != sol.end(); it++)
	{
		out << (*it) << ' ';
	}
	out << '\n';
	in.close();
	out.close();

	return 0;
}