Cod sursa(job #763268)

Utilizator PatrikStepan Patrik Patrik Data 1 iulie 2012 15:53:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
	#include<stdio.h>
	#include<vector>
	using namespace std ;
	FILE *f , *g ;
	int n , m ,l[50001] , np[50001] , viz[50001] ;
	vector<int> a[50001];
	vector<int>::iterator it;
	
	void citire();
	void solve();
	void tipar();
	
	int main()
	{
		citire();
		solve();
		tipar();
		return 0;
	}
	
	void citire()
	{
		int x , y;
		f=fopen("sortaret.in" , "r" );
		fscanf(f , "%d%d" , &n , &m );
		for(int i = 1 ; i<= m ; ++i )
		{
			fscanf(f , "%d%d" , &x , &y );
			a[x].push_back(y);
			np[y]++;
		}
		fclose(f);
	}
	
	void solve()
	{
		for(int i = 1 ; i<= n ; ++i )
			if(!np[i])
			{
				l[++l[0]] = i;
				viz[i] = 1;
			}
		for(int i = 1 ; i<= n ; ++i )
		{
			for( it = a[l[i]].begin() ; it < a[l[i]].end() ; ++it )
			{
				np[*it]--;
				if(np[*it] == 0)
					l[++l[0]] = *it;
			}
		}
	}
	
	void tipar()
	{
		g=fopen("sortaret.out" , "w" );
		for(int i = 1 ; i<= n ; ++i )
			fprintf(g , "%d " , l[i] );
		fclose(g);
	}