Cod sursa(job #1554086)

Utilizator cosminionutCosmin Ionut cosminionut Data 20 decembrie 2015 21:22:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

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


	int n, m;
	while (!S.empty())
	{
		n = S.back();
		S.pop_back();
		L.push_back(n);
		while (!Graf[n].empty())
		{
			m = Graf[n].back();
			incomingNodes[m]--;
			if(incomingNodes[m]==0)	S.push_back(m);
			Graf[n].pop_back();
		}
	}



	//afisare();
	for (vector<int>::iterator i = L.begin();i != L.end();i++)
		g << *i << " ";
	
	return 0;
}