Cod sursa(job #627962)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 31 octombrie 2011 03:06:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
FILE *in = fopen ("sortaret.in", "r"), *out = fopen ("sortaret.out", "w");

vector <int> graf[50001], sort;
queue <int> S;
int gradInterior[50001];

int main(){
	int n, m, i, j, x, y;
	
	fscanf (in, "%d %d", &n, &m);
	for (i = 0; i < m; i++){
		fscanf(in, "%d %d", &x, &y);
		graf[x].push_back(y);
		gradInterior[y]++;
	}
	
	for (i = 1; i <=n ; i++) if (gradInterior[i] == 0) S.push(i);
	while (!S.empty())
	{
		int nod = S.front();
		sort.push_back(nod);
		for (j = 0; j < graf[nod].size(); j++)
			if ( --gradInterior[graf[nod][j]] == 0) S.push(graf[nod][j]) ;
		S.pop();
	}
	
	for (i = 0; i < sort.size();  i++)
		fprintf (out, "%d ", sort[i]);
	return 0;
}