Cod sursa(job #1456575)

Utilizator tony.hegyesAntonius Cezar Hegyes tony.hegyes Data 1 iulie 2015 11:27:54
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 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 edge_mat[n][n], inDeg[n];
	
	// initialize default values
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			edge_mat[i][j] = 0;
		}
		inDeg[i] = 0;
	}
	
	// input data
	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
	int nodesWithIndegreeZero[n + 1];
	nodesWithIndegreeZero[0] = 0;
	
	// find nodes with no dependency
	for (int i = 0; i < n; i++) {
		if (inDeg[i] == 0) {
			nodesWithIndegreeZero[++(nodesWithIndegreeZero[0])] = i;
		}
	}
	
	// create the topological order
	int topologicalSort[n + 1];
	topologicalSort[0] = 0;
	
	int viz[n];
	for (int i = 0; i < n; i++) 
		viz[i] = 0;
	
	while(nodesWithIndegreeZero[0] != 0) {
		// add the dependency-free node to the sorted list and remove it from nodes to look at
		int node = nodesWithIndegreeZero[nodesWithIndegreeZero[0]--];
		topologicalSort[++(topologicalSort[0])] = node;
		
		// remove all dependencies to this node
		for (int i = 0; i < n; i++) {
			// if dependency exists
			if (edge_mat[node][i] == 1) {
				// remove dependency
				edge_mat[node][i] = 0;
				inDeg[i]--;
				
				// if no more dependencies, look at it in the future
				if (inDeg[i] == 0 && viz[i] = 0) {
					viz[i] = 1;
					nodesWithIndegreeZero[++(nodesWithIndegreeZero[0])] = i;
				}
			}
		}
	}
	
	// OUTPUT
	ofstream outdata("sortaret.out");
	for (int i = 1; i <= n; i++) {
		outdata << (topologicalSort[i] + 1) << " ";
	}
	outdata.close();
	return 0;
}