Cod sursa(job #415627)

Utilizator liviu12345Stoica Liviu liviu12345 Data 11 martie 2010 17:04:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream.h>
#include<vector>
#define maxn 100001

using namespace std;
vector < vector < int > > lista;
int sel[ maxn ],coada[maxn],n,m;
int main()
{
	int i,j,k;
	ifstream f ("sortaret.in");
	ofstream g ("sortaret.out");
	f>>n>>m;
	
	vector < int > temp;
	for( int i = 0; i <= n; ++i)
		lista.push_back( temp);
	while (f>>i>>j)
	{
		lista[i].push_back(j);
		sel[j]++;
		//lista[j].push_back(i);
		
	}
	int nr_elem = 0, coada[maxn];
	for( int i = 1; i <= n; ++i)
		if( sel[i] == 0)
			coada[ ++nr_elem] = i;
	for (i=1;i<=n;i++)
	{
		j = coada[i];
		int size = lista[j].size();
		for(k=0;k<size;k++)
		{
			sel[lista[j][k]]--;
			if( sel[lista[j][k]] == 0)
			{
				coada[ ++nr_elem] = lista[j][k];
			}
		}
			
			
	}
	for(i=1;i<=n;i++)
		g<<coada[i]<<" ";
	f.close();
	g.close();
	return 0;
	
}