Cod sursa(job #2001560)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 17 iulie 2017 01:03:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int> edge[50001], list;
int visited[50001], ideg[50001], n, m;


void Kahn()
{
	vector<int> sortedL;

	while (!list.empty())
	{
		int t = list.back();
		sortedL.push_back(t);
		list.pop_back();
		for (int i = 0; i < edge[t].size(); i++)
		{
			int q = edge[t][i];
			edge[t].erase(edge[t].begin());
			i--;
			ideg[q]--;
			if (ideg[q] == 0)
				list.push_back(q);
		}
	}

	for (vector<int>::iterator it = sortedL.begin(); it != sortedL.end(); it++)
		g << *it << " ";

}

int main()
{
	int i;
	f >> n >> m;

	for (i = 0; i < m; i++)
	{
		int c, d;
		f >> c >> d;
		edge[c].push_back(d);
		ideg[d]++;
	}

	for (i = n; i > 0; i--)
		if (ideg[i] == 0)
			list.push_back(i);
	
	Kahn();

	return 0;
}