Cod sursa(job #384091)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 19 ianuarie 2010 09:17:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>
#include <vector>
using namespace std;

vector <int> A[50099];

int rang[50099], c[50099];
int x, y, i, j, n, m, p=1, u=0;

int main (){

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

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

	for (i = 1 ; i <= n ; i++)
		if (rang[i] == 0){
			c[++u] = i;
		}

	while (p<=u){

		for (j = 0 ; j < A[c[p]].size() ; j++){
			rang[A[c[p]][j]]--;
			if (rang[A[c[p]][j]] == 0) c[++u] = A[c[p]][j];
		}

		p++;

	}

	for (i = 1 ; i <= n ; i++)
		fscanf (g, "%d", c[i]);

	fclose(f);
	fclose(g);
	return 0;
}