Cod sursa(job #504881)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 29 noiembrie 2010 12:12:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb

#include <cstdio>
#include <deque>
#include <fstream>
#include <vector>

using namespace std;

#define k 50001
#define pb push_back

vector<int> v[k];
deque<int> q;
int c[k];
int n,m;

void read (){
	
	ifstream in ("sortaret.in");
	in>>n>>m;
	for(int a,b,i=1;i<=m;++i){
		in>>a>>b;
		v[a].pb(b);
		++c[b];
		}
		in.close ();
	
	}
	
	void sorttop (){
		
		for(int i=1;i<=n;++i)
		if(c[i]==0)
		q.pb(i);
		for(int j,i=1;i<=n;++i){
			j=q[i-1];
			for(vector<int>::iterator it = v[j].begin();it != v[j].end();++it){
				--c[*it];
				if(c[*it] == 0)
				q.pb(*it);
				}
			}
		
		}
		
		void write (){
			
			freopen ("sortaret.out","w",stdout);
			for(;!q.empty();q.pop_front())
			printf("%d ",q.front());
			printf("\n");
			
			}

int main ()
{
	
	read ();
	sorttop ();
	write ();
	
	return 0;}