Cod sursa(job #2888918)

Utilizator victorzarzuZarzu Victor victorzarzu Data 11 aprilie 2022 22:55:34
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <fstream>
#include <iostream>
#include <queue>

using std::vector;
using std::string;
using std::ifstream;
using std::ofstream;
using std::set;
using std::pair;
using std::queue;

#define arc pair<int, int>
#define nod first
#define cost second
#define oo 0x3f3f3f3f


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

	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 (const auto& vecin : graf[node]) {
			if (!viz[vecin]) {
				dfs(vecin);
			}
		}
		topo.push_back(node);
	}

	void dfst(int node, vector<int>& componenta) {
		viz[node] = false;
		componenta.push_back(node);
		for (const 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:
	Solve(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};

	void print() {
		
		ofstream out(output_file);
		solve();
		
		out << result.size() << '\n';
		for (const auto& componenta : result) {
			for (const auto& node : componenta) {
				out << node << " ";
			}
			out << '\n';
		}


		out.close();
	}

	~Solve() {
		delete[] graf;
	}
};

int main() {

	Solve s = Solve("ctc.in", "ctc.out");
	s.print();

	return 0;
}