Cod sursa(job #1456551)

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

int main(int argc, char **argv)
{
	// input data
	ifstream indata("sortaret.in");
	
	int n, m;
	indata >> n >> m;
	int edge_mat[n][n];
	int inDeg[n];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			edge_mat[i][j] = 0;
		}
		inDeg[i] = 0;
	}
	
	int x, y;
	for (int i = 0; i < m; i++) {
		indata >> x >> y;
		edge_mat[x-1][y-1] = 1;
		inDeg[y-1]++;
	}
	
	indata.close();
	
	// topological sort of nodes
	vector<int> nodesWithNoIncomingEdges;
	for (int i = 0; i < n; i++) {
		if (inDeg[i] == 0) {
			nodesWithNoIncomingEdges.push_back(i);
		}
	}
	
	vector<int> topologicalSort;
	while(nodesWithNoIncomingEdges.size() != 0) {
		int last = nodesWithNoIncomingEdges.back();
		nodesWithNoIncomingEdges.pop_back();
		topologicalSort.push_back(last);
		
		for (int i = 0; i < n; i++) {
			// if a node has a dependency on this one
			// remove it (remove the edge)
			if(edge_mat[last][i] == 1) {
				edge_mat[last][i] = 0;
				inDeg[i]--;
				
				// if that was the only dependency, 
				// add node to topSort
				if (inDeg[i] == 0) {
					nodesWithNoIncomingEdges.push_back(i);
				}
			}
		}
	}
	
	// output data
	ofstream outdata("sortaret.out");
	for (size_t i = 0; i < topologicalSort.size(); i++) {
		outdata << (topologicalSort[i] + 1) << " ";
	}
	outdata.close();
	return 0;
}