Cod sursa(job #2888566)

Utilizator victorzarzuZarzu Victor victorzarzu Data 11 aprilie 2022 16:28:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <vector>
#include <string>
#include <fstream>
#include <stack>

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

class Biconex {
private:
	string input_file;
	string output_file;
	stack<int> s;
	vector<int> dfn, low;
	vector<int>* graf;
	vector<vector<int>> result;

	void read() {
		ifstream in(input_file);
		int n, m, x, y;
		
		in >> n >> m;

		dfn.resize(n + 1, 0);
		low.resize(n + 1, 0);
		graf = new vector<int>[n + 1];

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

		in.close();
	}

	void dfs(int node, int level) {
		dfn[node] = low[node] = level;
		s.push(node);

		for (const auto& vecin : graf[node]) {
			if (dfn[vecin]) {
				low[node] = std::min(low[node], dfn[vecin]);
			}
			else {
				dfs(vecin, level + 1);
				low[node] = std::min(low[node], low[vecin]);

				if (low[vecin] >= dfn[node]) {
					vector<int> componenta;
					componenta.push_back(node);
					int x;
					do {
						x = s.top();
						s.pop();
						componenta.push_back(x);
					} while (x != vecin);
					result.push_back(componenta);
				}
			}
		}
	}

	void solve() {
		read();

		dfs(1, 1);
	}

public:
	Biconex(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{};

	void print() {
		solve();
		ofstream out(output_file);

		out << result.size()<<'\n';

		for (const auto& componenta : result) {
			for (const auto& nod : componenta) {
				out << nod << " ";
			}
			out << '\n';
		}

		out.close();
	}

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

int main() {

	Biconex biconex = Biconex("biconex.in", "biconex.out");
	biconex.print();

	return 0;
}