Cod sursa(job #2510217)

Utilizator studentdin19bluredman studentdin19 Data 16 decembrie 2019 00:39:33
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb


#include <map>
#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

template <typename T>
class Graph {
public:
	map<T, set<T>> edges;

	void addEdge(T const from, T to) {
		edges[from].insert(to);
	}

	vector<T> topologicSort() {
		set<T> vis;
		vector<T> ret;
		for (auto const & v : edges)
			if (vis.find(v.first) == vis.end())
				dfs(v.first, vis, ret);
		
		return ret;
	}

	void dfs(const T&v, set<T>& vis, vector<T>& ret) {
		vis.insert(v);

		for (auto const &  e : edges[v])
			if (vis.find(e) == vis.end())
				dfs(e, vis, ret);
		ret.emplace_back(v);
	}
	
};


int main() {
	int Edges;
	cin >> Edges;
	Graph<int> A;

	for (cin >> Edges;Edges!=0; Edges--) {
		int from, to; 
		cin >> from >> to;
		A.addEdge(from, to);
	}

	auto rez = A.topologicSort();

	for (auto it : rez)
		cout << it << ' ';

}