Cod sursa(job #2888216)

Utilizator victorzarzuZarzu Victor victorzarzu Data 10 aprilie 2022 20:21:03
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 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[node]) {
				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';
		}

		out.close();
	}

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

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

	return 0;
}