Cod sursa(job #2082065)

Utilizator IulianBobocBoboc Iulian IulianBoboc Data 5 decembrie 2017 17:52:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
using namespace std;
#define nMax 50001

struct nod{ 
	nod *next;
	int value;
};

nod *nodes[nMax], *topologicalSorted;
bool visited[nMax];

void addNewNode(nod* &node, int value) {
	if (node == NULL) {
		node = new nod;
		node->value = value;
		node->next = NULL;
	}
	else {
		nod *newNod = new nod;
		newNod->value = value;
		newNod->next = node;
		node = newNod;
	}
}

void topologicalSort(int node) {
	visited[node] = true;
	for (nod *p = nodes[node]; p != NULL; p = p->next) {
		if (!visited[p->value]) {
			topologicalSort(p->value);
		}
	}
	addNewNode(topologicalSorted, node);
}

int main() {
	ifstream inFile("sortaret.in");
	ofstream outFile("sortaret.out");
	int n, m, i, a, b;
	inFile >> n >> m;
	for (i = 1; i <= m; ++i) {
		inFile >> a >> b;
		addNewNode(nodes[a], b);
	}
	
	for (i = 1; i <= n; ++i) {
		if (!visited[i]) {
			topologicalSort(i);
		}
	}
	for (nod *p = topologicalSorted; p != NULL; p = p->next) {
		outFile << p->value << " ";
	}

	inFile.close();
	outFile.close();
	return 0;
}