Cod sursa(job #1808094)

Utilizator zurzic_doruzurzic zeljko zurzic_doru Data 17 noiembrie 2016 12:31:30
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <list>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	
	int n, m, x, y;
	FILE *fin = fopen("sortaret.in", "r");
	FILE *fout = fopen("sortaret.out", "w");
	fscanf(fin, "%d%d", &n, &m);

	vector<int> number_in_edges(n + 1);

	vector<list<int>> graph(n + 1);

	for(int i = 1; i <= m; i++) {
		fscanf(fin, "%d%d", &x, &y);
		graph[x].push_back(y);
		number_in_edges[y]++;
	}

	list<int> sorted_elements;
	queue<int> no_in_edges;

	for(int i = 1; i <= m; i++) {
		if(number_in_edges[i] == 0)
			no_in_edges.push(i);
	}

	list<int>::iterator neighbors_iterator;

	while(!no_in_edges.empty()) {
		int taken_vertex = no_in_edges.front();
		no_in_edges.pop();
		sorted_elements.push_back(taken_vertex);

		for(neighbors_iterator = graph[taken_vertex].begin(); 
			neighbors_iterator != graph[taken_vertex].end(); ++neighbors_iterator) {
		
				int vertex = *neighbors_iterator;
				//neighbors_iterator = graph[taken_vertex].erase(neighbors_iterator);
				number_in_edges[vertex]--;
				if(number_in_edges[vertex] == 0)
					no_in_edges.push(vertex);
		}
	}

	for(neighbors_iterator = sorted_elements.begin(); 
		neighbors_iterator != sorted_elements.end(); ++neighbors_iterator) {
			fprintf(fout, "%d ", *neighbors_iterator);
	}


}