Cod sursa(job #301575)

Utilizator katakunaCazacu Alexandru katakuna Data 8 aprilie 2009 11:56:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#include <vector>

#define Nmax 50010

vector <int> V[Nmax];
vector  <int> Q;
int n, m, i, x, y, N, G[Nmax];

void citire(){

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

	fscanf(f,"%d %d", &n, &m);
	for(i = 1; i <= m; i++){
		fscanf(f,"%d %d",&x, &y);
		V[x].push_back(y);
		G[y]++;
	}
	
	fclose(f);

}


void solve(){

	int i, p = 0, nod, fiu;
	for(i = 1; i <= n; i++)
		if( !G[i] ){
			N++; 
			Q.push_back(i);
		}
	
	for( ; N != n; p++){
		nod = Q[p];
		for(i = 0; i < V[nod].size(); i++){
			fiu = V[nod][i];
			G[fiu]--;
			if( !G[fiu] ){
				Q.push_back(fiu);
				N++;
			}
		}
		
	}

}


void afisare(){

	FILE *g = fopen("sortaret.out", "w");
	
	for(i = 0; i < Q.size(); i++)
		fprintf(g,"%d ",Q[i]);
	
	fclose(g);

}


int main(){

	citire();
	solve();
	afisare();

	return 0;
}