Cod sursa(job #1585274)

Utilizator sebii_cSebastian Claici sebii_c Data 30 ianuarie 2016 21:42:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/**@brief Generic graph data structure.
 */
template <class T>
class graph {
public:
    explicit graph(const vector<pair<T, T>>& pairs, const vector<T>& node)
	: nodes(node.begin(), node.end()) {
	for (auto& p : pairs) {
	    edges[p.first].push_back(p.second);
	}
    }

    /**@brief Returns a topological sort of the graph.
     */
    vector<T> toposort() {
	unordered_map<T, int> in_degree;
	for (auto& p : edges) {
	    for (auto& node : p.second) {
		in_degree[node]++;
	    }
	}
	
	vector<T> result;
	queue<T> topo;
	for (auto& node : nodes) {
	    if (in_degree[node] == 0)
		topo.push(node);
	}

	while (!topo.empty()) {
	    auto node = topo.front();
	    topo.pop();
	    result.push_back(node);
	    for (auto& next : edges[node]) {
		in_degree[next]--;
		if (in_degree[next] == 0) {
		    topo.push(next);
		}
	    }
	}

	return result;
    }
    
private:
    unordered_map<T, vector<T>> edges;
    unordered_set<T> nodes;
};

int main() {
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n, m; fin >> n >> m;
    vector<int> nodes;
    for (int i = 0; i < n; ++i) {
	nodes.push_back(i + 1);
    }
    vector<pair<int, int>> pairs;
    for (int i = 0; i < m; ++i) {
	int a, b; fin >> a >> b;
	pairs.push_back(pair<int, int>(a, b));
    }

    graph<int> g(pairs, nodes);
    auto result = g.toposort();
    for (auto x : result) {
	fout << x << " ";
    }
    fout << endl;
    
    return 0;
}