Cod sursa(job #2888930)

Utilizator victorzarzuZarzu Victor victorzarzu Data 11 aprilie 2022 23:03:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>

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

#define oo 0x3f3f3f3f


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

	void read() {
		ifstream in(input_file);

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

		int x, y;
		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 lvl) {
		dfn[node] = low[node] = lvl;
		s.push(node);

		for (const int& vecin : graf[node]) {
			if (dfn[vecin]) {
				low[node] = std::min(low[node], dfn[vecin]);
			}
			else {
				dfs(vecin, lvl + 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:
	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("biconex.in", "biconex.out");
	s.print();

	return 0;
}