Cod sursa(job #145845)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 29 februarie 2008 16:21:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 1 << 16;

int N, M, V[NMAX];
vector <int> G[NMAX];
queue <int> Q;

void read(void) {
	FILE *fin = fopen("sortaret.in", "rt");
	int i, u, v;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &u, &v);
		G[u].push_back(v); ++V[v];
	}

	fclose(fin);
}

void solve(void) {
	FILE *fout = fopen("sortaret.out", "wt");
	vector <int> :: iterator j;
	int i;

	for (i = 1; i <= N; ++i)
		if (V[i] == 0)
			Q.push(i);
	
	for (; !Q.empty(); Q.pop()) {
		i = Q.front();
		fprintf(fout, "%d ", i);

		for (j = G[i].begin(); j != G[i].end(); ++j)
			if (--V[*j] == 0)
				Q.push(*j);
	}
	fprintf(fout, "\n");

	fclose(fout);
}

int main(void) {

	read();

	solve();

	return 0;
}