Cod sursa(job #917634)

Utilizator NicuCJNicu B. NicuCJ Data 18 martie 2013 10:43:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
vector<int> vec[50001];
int depinde[50001];
int a, b, n, m, i, cx;
queue<int> coada;
int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	f>>n>>m;
	for(i=1; i<=m; i++)
	{
		f>>a>>b;
		vec[a].push_back(b);
		depinde[b]++;
	}
	for(i=1; i<=n; i++)
	{
		if(!depinde[i])
			coada.push(i);
	}
	while(!coada.empty())
	{
		cx=coada.front();
		coada.pop();
		for(i=0; i<vec[cx].size(); i++)
		{
			depinde[vec[cx][i]]--;
			if(!depinde[vec[cx][i]])
				coada.push(vec[cx][i]);
		}
		g<<cx<<" ";
	}
}