Cod sursa(job #780698)

Utilizator ml.vladareanVladarean Maria ml.vladarean Data 20 august 2012 23:48:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
using namespace std;

#define max 50001

int N, M, i, contor, n1, n2, grad[max], coada[max] ;
vector <int> Muchii[max];


void read()
{
	ifstream fin("sortaret.in");
	fin>>N>>M;
	for(i=1;i<=M;++i)
	{
		fin>>n1>>n2;
		Muchii[n1].push_back(n2); // pun muchiile pe care le face n1 cu alte noduri
		++grad[n2]; // cresc gradul lui n2 ( ca sa-l compar cu 0 dupa iteratii ) 
		
	}
}

void write()
{
	ofstream fout("sortaret.out");
	for(i=1;i<=N;++i)
		fout<<coada[i]<<" ";
	fout<<"\n";
}

void solve()
{
	vector<int>::iterator it;
	
	for(i=1;i<=N;++i)
		if(grad[i]==0)
			coada[++contor]=i;  //bag toate nodurile care eu la inceput gradul 0
	

	//parcurg coada si elimin muchiile pe care le formeaza nodurile cu gradul 0; scad gradul nodurilor in care intrau muchiile; daca ajung 0 le bag in coada
	int aux;
	for(i=1;i<=N;++i)
	{
		aux = coada[i];
		for( it = Muchii[aux].begin() ; it != Muchii[aux].end() ; ++it )
		{
			--grad[*it];
			if( grad[*it] == 0 )
				coada[++contor] = *it ;
				
			
		}
		

	}

}

int main()
{

	read();
	solve();
	write();


	return 0;
}