Cod sursa(job #759124)

Utilizator aranhilChivu Stefan Iulian aranhil Data 16 iunie 2012 20:20:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <list>

using namespace std;

int main() {

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

	int n, m;
	fscanf(f, "%d %d", &n, &m);

	int *gr = new int[n];
	for(int i = 0; i < n; i++) gr[i] = 0;
	list<int> liste[n];
	int *Q = new int[n], c = 0;

	for(int i = 0; i < m; i++) {
		int x, y;
		fscanf(f, "%d %d", &x, &y);
		liste[x - 1].push_back(y - 1);
		gr[y - 1] ++;
	}

	for(int i = 0; i < n; i++) {
		if(gr[i] == 0) 
			Q[c++] = i;
	}

	for(int i = 0; i < n; i++) {
		for(list<int>::iterator j = liste[i].begin(), l = liste[i].end(); j != l; j++) {
			gr[*j]--;
			if(gr[*j] == 0) {
				Q[c++] = *j;
			}
		}
	}

	for(int i = 0; i < c; i++)
		fprintf(g, "%d ", Q[i] + 1);

	fclose(f);
	fclose(g);

	return 0;
}