Cod sursa(job #563309)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 24 martie 2011 21:56:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<vector>
using namespace std;
#define maxN 50005

FILE*f=fopen("sortaret.in","r");
FILE*g=fopen("sortaret.out","w");

int N,M,i,A,B,C[maxN],grd[maxN];

vector<int>V[maxN];

void tplgsort () {
	
	int nod ; int p , u = 0 ;
	
	for ( int i = 1 ; i <= N ; ++i ){
		if ( !grd[i] )
			C[++u] = i ;
	}
	
	for ( p = 1 ; p <= u ; ++p ){
		
		nod = C[p];
		
		for ( int i = 0 ; i < V[ nod ].size() ; ++i ){
			
			--grd[ V[nod][i] ];
			if ( !grd[ V[nod][i] ] )
				C[ ++u ] = V[nod][i] ;
			
		}
		
	}
	
}

int main () {
	
	fscanf(f,"%d %d",&N,&M);
	
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d",&A,&B);
		V[A].push_back(B);
		++grd[B];
	}
	
	tplgsort();
	
	for ( i = 1 ; i <= N ; ++i ){
		fprintf(g,"%d ",C[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}