Cod sursa(job #2888219)

Utilizator victorzarzuZarzu Victor victorzarzu Data 10 aprilie 2022 20:26:06
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <vector>
#include <string>
#include <fstream>

using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;


class TareConexe {
private:
	int n, m;
	string input_file, output_file;
	vector<int>* graf;
	//vector<int>* graft;
	vector<bool> viz;
	vector<int> topo;
	vector<vector<int>> result;

	void read() {
		ifstream in(input_file);
		in >> n >> m;

		graf = new vector<int>[n + 1];
		//graft = new vector<int>[n + 1];
		viz.resize(n + 1, false);

		int x, y;
		for (int i = 1; i <= m; ++i) {
			in >> x >> y;
			graf[x].push_back(y);
			//graft[y].push_back(x);
		}

		in.close();
	}

	void dfs(int node) {
		viz[node] = true;
		for (auto vecin : graf[node]) {
			if (!viz[vecin]) {
				dfs(vecin);
			}
		}

		topo.push_back(node);
	}

	//void dfst(int node, vector<int>& componenta) {
	//	componenta.push_back(node);
	//	viz[node] = false;
	//	for (auto vecin : graft[node]) {
	//		if (viz[vecin]) {
	//			dfst(vecin, componenta);
	//		}
	//	}

	//}

	void solve() {
		read();

		for (int i = 1; i <= n; ++i) {
			if (!viz[i]) {
				dfs(i);
			}
		}

		//for (vector<int>::reverse_iterator it = topo.rbegin(); it != topo.rend(); ++it) {
		//	if (viz[*it]) {
		//		vector<int> componenta;
		//		dfst(*it, componenta);
		//		result.push_back(componenta);
		//	}
		//}
	}

public:
	TareConexe(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }, topo(), result(){};


	void print() {
		solve();

		ofstream out(output_file);
		//out << result.size() << '\n';

		//for (auto componenta : result) {
		//	for (auto node : componenta) {
		//		out << node << " ";
		//	}
		//	out << '\n';
		//}
		for (vector<int>::reverse_iterator it = topo.rbegin(); it != topo.rend(); ++it) {
			out << *it << " ";
		}

		out.close();
	}

	~TareConexe() {
		delete[] graf;
		//delete[] graft;
	}
};

int main() {
	TareConexe t = TareConexe("sortare.in", "sortare.out");
	t.print();

	return 0;
}