Cod sursa(job #1553434)

Utilizator cosminionutCosmin Ionut cosminionut Data 19 decembrie 2015 20:48:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <list>
#include <cstring>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
list<int> Graf[50001], L, S;
bool visited[50001];
int N, M;

void citire()
{
	int i, x, y;
	f >> N >> M;
	for (i = 0;i < M;i++)
	{
		f >> x >> y;
		visited[y] = 1;
		Graf[x].push_back(y);
	}
	for (i = 1;i <= N;i++)
		if (!visited[i] && Graf[i].begin() != Graf[i].end())
			S.push_back(i);
	memset(visited, 0, sizeof(visited));
}
void afisare()
{
	
	for (int i = 1;i <= N;i++)
		if (!visited[i])
			g << i << " ";
	for (list<int>::iterator i = L.begin();i != L.end();i++)
		g << *i << " ";
}

int main()
{
	citire();
	int n, m;

	while (S.begin() != S.end())
	{
		n = *(S.begin());
		S.pop_front();
		if (visited[n] == false)
		{
			L.push_back(n);
			visited[n] = true;
		}
		while (Graf[n].begin()!=Graf[n].end())
		{
			m = *(Graf[n].begin());
			S.push_back(m);
			Graf[n].pop_front();
		}
	}
	
	afisare();

	return 0;
}