Cod sursa(job #565711)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2011 10:47:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
using namespace std;
#define dim 50002

vector <int> v[dim]; 
int grad[dim], sf, coada[dim];
ofstream fout("sortaret.out");
void sortare()
{
	int inc=1;
	
	while(inc<=sf)
	{
		int x=coada[inc];
		fout<<x <<" ";
			
		for(int k=0;k<v[x].size();++k)
		{
			--grad[v[x][k]];
			if(grad[v[x][k]]==0)
			{
				++sf;
				coada[sf]=v[x][k];
			}
		}
		++inc;
	}
}

int main()
{
	ifstream fin("sortaret.in");
	int n, m, i, a, b;
	fin>>n >>m;
	
	for(i=1;i<=m;++i)
	{
		fin>> a >>b;
		v[a].push_back(b);
		++grad[b];
	}
	
	for(i=1;i<=n;++i)
		if(grad[i]==0)
		{
			++sf;
			coada[sf]=i;
		}
	
	
	sortare();
		
		
	return 0;
}