Cod sursa(job #1456584)

Utilizator tony.hegyesAntonius Cezar Hegyes tony.hegyes Data 1 iulie 2015 11:44:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

int main(int argc, char **argv)
{
	// INPUT
	ifstream indata("sortaret.in");
	
	int n, m;
	indata >> n >> m;
	
	int inDeg[n];
	vector<int> edges[n];
	for (int i = 0; i < n; i++) {
		inDeg[i] = 0;
	}
	
	// input data
	int x, y;
	for (int i = 0; i < m; i++) {
		indata >> x >> y;
		// set edges and inDegree of nodes
		edges[x - 1].push_back(y - 1);
		inDeg[y - 1]++;
	}
	
	indata.close();
	
	// TOPOLOGICAL SORT
	int topologicalSort[n + 1];
	topologicalSort[0] = 0;
	
	// first add all nodes which don't have dependencies
	for (int i = 0; i < n; i++) {
		if (inDeg[i] == 0) {
			topologicalSort[++topologicalSort[0]] = i;
		}
	}
	
	// now browse through nodes and remove dependencies
	for (int i = 1; i <= n; i++) {
		int dependencyFreeNode = topologicalSort[i];
		// remove all edges going out from this node and update inDegrees accordingly
		for(vector<int>::iterator vit = edges[dependencyFreeNode].begin(); vit < edges[dependencyFreeNode].end(); vit++) {
			inDeg[*vit]--;
			if (inDeg[*vit] == 0) {
				topologicalSort[++topologicalSort[0]] = *vit;
			}
		}
	}
	
	// OUTPUT
	ofstream outdata("sortaret.out");
	for (int i = 1; i <= n; i++) {
		outdata << (topologicalSort[i] + 1) << " ";
	}
	outdata.close();
	return 0;
}