Cod sursa(job #1456544)

Utilizator tony.hegyesAntonius Cezar Hegyes tony.hegyes Data 1 iulie 2015 10:20:31
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			edge_mat[i][j] = 0;
		}
	}
	
	int x, y;
	for (int i = 0; i < m; i++) {
		indata >> x >> y;
		edge_mat[x-1][y-1] = 1;
	}
	
	indata.close();
	
	// topological sort of nodes
	vector<int> topologicalSort;
	vector<int> nodesWithNoIncomingEdges;
	for (int i = 0; i < n; i++) {
		bool hasIncoming = false;
		for (int j = 0; j < n; j++) {
			if (edge_mat[j][i] == 1) {
				hasIncoming = true;
				break;
			}
		}
		if (hasIncoming == false) {
			nodesWithNoIncomingEdges.push_back(i + 1);
		}
	}
	
	
	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-1][i] == 1) {
				edge_mat[last-1][i] = 0;
				
				// if that was the only dependency, 
				// add node to topSort
				int sum = 0;
				for (int j = 0; j < n; j++) {
					sum += edge_mat[j][i];
				}
				if (sum == 0) {
					nodesWithNoIncomingEdges.push_back(i + 1);
				}
			}
		}
	}
	
	// output data
	ofstream outdata("sortaret.out");
	for (int i = 0; i < topologicalSort.size(); i++) {
		outdata << topologicalSort[i] << " ";
	}
	outdata.close();
	return 0;
}