Cod sursa(job #1705070)

Utilizator laurentiu.piciuPiciu Laurentiu laurentiu.piciu Data 19 mai 2016 21:19:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

int N, M;

using Graph = std::vector<std::vector<int> >;
Graph graph;


std::vector<int> kahn_topsort(std::vector<int>& grad_in) {
    std::vector<int> topologicalSort;
    int visited = 0;

    std::queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (grad_in[i] == 0) {
            q.push(i);
        }
    }
 
    while (!q.empty()) {
        int curr_node = q.front();
        q.pop();
        topologicalSort.push_back(curr_node);

        visited++;

        for (unsigned i = 0; i < graph[curr_node].size(); ++i) {
        	int neigh = graph[curr_node][i];
        	grad_in[neigh]--;

        	if (grad_in[neigh] == 0) {
        		q.push(neigh);
        	}
        }
    }
 
    if (visited != N) {
        std::cerr << "CICLU\n";
    }
 
   	return topologicalSort;
}

int main() {
	std::ifstream f("sortaret.in");
	std::ofstream g("sortaret.out");

	f >> N >> M;

	graph.resize(N+1);
	std::vector<int> grad_in(N+1, 0); /* Calculez gradul_in pentru fiecare nod */

	for (int i = 0; i < M; ++i) {
		int from, to;
		f >> from >> to;
		graph[from].push_back(to);
		grad_in[to]++;
	}

	std::vector<int> topSort = kahn_topsort(grad_in);
	for (int i = 0; i < topSort.size(); ++i) {
		g << topSort[i] << " ";
	}


	f.close(); g.close();

	return 0;
}