Cod sursa(job #3221276)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 6 aprilie 2024 14:50:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector < int > v[100005];
int n, m, x, y, timp;
int disc[100005], low[100005];
int tata[100005];
bool viz[100005];
stack < pair < int, int > > st;
vector < int > biconex;
vector < vector < int > > components;

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		f >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void dfs_l(int nod) {
	low[nod] = disc[nod] = ++timp;
	for (auto k : v[nod]) {
		if (disc[k] == 0) {
			tata[k] = nod;
			dfs_l(k);
			low[nod] = min(low[nod], low[k]);
		}
		else if (k != tata[nod]) {
			low[nod] = min(low[nod], disc[k]);
		}
	}
}

void creare_biconex(int a, int b) {
	biconex.clear();
	int x = st.top().first, y = st.top().second;
	while (x != a || y != b) {
		biconex.push_back(y);
		st.pop();
		x = st.top().first; y = st.top().second;
	}
	st.pop();
	biconex.push_back(y); biconex.push_back(x);
	components.push_back(biconex);
}

bool punct_art(int x, int fiu) {
	if (low[fiu] >= disc[x]) return 1;
	return 0;
}

void dfs(int nod) {
	viz[nod] = 1;
	for (auto k : v[nod]) {
		if (!viz[k]) {
			st.push({ nod, k });
			dfs(k);
			if (punct_art(nod, k)) {
				creare_biconex(nod, k);
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= n; i++) {
		if (disc[i] == 0) dfs_l(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!viz[i]) dfs(i);
	}
}

void print() {
	g << components.size() << '\n';
	for (auto w : components) {
		for (auto p : w) {
			g << p << " ";
		}
		g << '\n';
	}
}

int main() {
	read();
	solve();
	print();
	return 0;
}