Cod sursa(job #290782)

Utilizator mist000000 mist Data 28 martie 2009 18:25:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>

using namespace std;

struct nod {
	unsigned int vertex;
	nod *nxt;
};

int main()
{
	unsigned int N;
	long M;

	fstream fin("sortaret.in", ios::in);
	fin >> N >> M;

	nod *freeNodes = NULL;
	nod* successors[N];
	unsigned int inDegree[N];

	for (unsigned int i = 0; i < N; i++) {
		successors[i] = NULL;
		inDegree[i] = 0;
	}

	while (M--) {
		unsigned int x, y;
		fin >> x >> y;
		x--;
		y--;

		inDegree[y]++;

		nod *newNode = new nod;
		newNode->vertex = y;
		newNode->nxt = successors[x];
		successors[x] = newNode;
	}

	fin.close();

	for (unsigned int i = 0; i < N; i++)
		if (inDegree[i] == 0) {
			nod *newNode = new nod;
			newNode->nxt = freeNodes;
			newNode->vertex = i;
			freeNodes = newNode;
		}

	fstream fout("sortaret.out", ios::out);

	while (freeNodes) {
		nod *crtNode = freeNodes;
		freeNodes = freeNodes->nxt;
		fout << crtNode->vertex + 1 << ' ';

		nod *succ = successors[crtNode->vertex];
		successors[crtNode->vertex] = NULL;
		while (succ) {
			if(--inDegree[succ->vertex] == 0) {
				nod *newFree = new nod;
				newFree->nxt = freeNodes;
				newFree->vertex = succ->vertex;
				freeNodes = newFree;
			}
			succ = succ->nxt;
		}
	}

	fout.close();

	return 0;
}