Cod sursa(job #1585216)

Utilizator sebii_cSebastian Claici sebii_c Data 30 ianuarie 2016 21:02:35
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#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) {
	for (auto& p : pairs) {
	    edges[p.first].push_back(p.second);
	}
    }

    /**@brief Returns a topological sort of the graph.
     */
    vector<T> toposort() {
	unordered_set<T> branch;
	for (auto& p : edges) {
	    for (auto& neigh : p.second)
		branch.insert(neigh);
	}
	
	vector<T> result;
	for (auto& p : edges) {
	    if (!branch.count(p.first)) {
		search(p.first, result);
		break;
	    }
	}

	return result;
    }
    
private:
    void search(T node, vector<T>& result) {
	result.push_back(node);
	if (!edges[node].empty()) {
	    for (auto neigh : edges[node]) {
		search(neigh, result);
	    }
	}
    }
    
    unordered_map<T, vector<T>> edges;
};

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

    int n, m; fin >> n >> m;
    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);
    auto result = g.toposort();
    for (auto x : result) {
	fout << x << " ";
    }
    fout << endl;
    
    return 0;
}