Cod sursa(job #3196382)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 23 ianuarie 2024 19:35:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.29 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif

const int nmax = 1e5 + 7;
vector<int> g[nmax]; // graful nostru
int depth[nmax]; // adancimea nodului i
int viz[nmax]; // vizitat sau nu
int low[nmax]; // low[i] = cea mai mica adancime la care putem ajunge pornind din i in arborele dfs,
// dat fiind ca avem voie sa folosim o muchie "verde" (de intoarcere) o singura data
int ancestor[nmax]; // tatal direct al nodului i in arborele dfs

void dfs(int nod, int tata, int adancime) {
	depth[nod] = adancime;
	ancestor[nod] = tata;
	viz[nod] = 1;

	for (auto vecin : g[nod]) {
		if (vecin == tata || viz[vecin]) continue;
		dfs(vecin, nod, adancime + 1);
	}

	return;
}

void dfs_low(int nod, int tata) {
	low[nod] = depth[nod];

	for(auto vecin : g[nod]) {
		if(vecin == tata || depth[vecin] > depth[nod]) continue;

		// am gasit o muchie de intoarcere!
		// cerr << "Intoarcere: " << nod << " " << vecin << "\n";
		low[nod] = min(low[nod], depth[vecin]);
	}

	// altfel presupunem ca incercam o muchie "rosie" catre un fiu

	for(auto vecin : g[nod]) {
		if(vecin == tata || depth[vecin] != depth[nod] + 1) continue;

		// incercam o muchie "rosie" catre fiu
		dfs_low(vecin, nod);

		// acum stim low[vecin] pentru ca am apelat dfs_low pe vecin
		// deci putem updata low[nod] cu low[vecin]

		low[nod] = min(low[nod], low[vecin]);
	}

	return;
}

vector<int> puncte_critice;

void dfs_critice(int node, int tata) {
	bool este_critic = false;
	int nr_fii = 0;

	for(auto vec : g[node]) {
		if(vec == tata) continue;
		if(depth[vec] != depth[node] + 1) continue;

		++nr_fii;

		if(low[vec] >= depth[node]) {
			este_critic = true;
		}

		dfs_critice(vec, node);
	}

	// si avem 2 cazuri, fiindca radacina este punct critic daca are mai mult de 1 fiu
	// si chiar daca este_critic == false pentru radacina

	if(tata == 0 /* suntem in radacina */ && nr_fii >= 2) {
		este_critic = true;
	}

	if(este_critic) {
		puncte_critice.push_back(node);
	}
}

vector<pair<int, int>> poduri;

void dfs_poduri(int node, int tata) {
	for(auto vec : g[node]) {
		if(vec == tata) continue;
		if(depth[vec] != depth[node] + 1) continue;

		if(low[vec] > depth[node]) {
			poduri.push_back({node, vec});
		}

		dfs_poduri(vec, node);
	}
}

vector<vector<int>> biconexe_pe_noduri;
stack<int> dfs_stack;

void dfs_biconexe(int node, int tata) {
	dfs_stack.push(node);

	for(auto vec : g[node]) {
		if(vec == tata) continue;
		if(depth[vec] != depth[node] + 1) continue;

		dfs_biconexe(vec, node);

		if(low[vec] >= depth[node]) {
			// am gasit o componenta biconexa
			vector<int> comp_biconexa;
			while(dfs_stack.top() != vec) {
				comp_biconexa.push_back(dfs_stack.top());
				dfs_stack.pop();
			}
			comp_biconexa.push_back(vec);
			comp_biconexa.push_back(node);
			dfs_stack.pop();

			biconexe_pe_noduri.push_back(comp_biconexa);
		}
	}
}

int main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y; cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	dfs(1, 0, 1);

	#ifdef LOCAL
		cerr << "Depth: " << "\n";
		for (int i = 1; i <= n; ++i) {
			cerr << depth[i] << " ";
		}
		cerr << "\n";
	#endif

	dfs_low(1, 0);

	// Eu vreau sa ma uit care noduri au low[i] == depth[i]

	#ifdef LOCAL
		cerr << "Low: " << "\n";
		for (int i = 1; i <= n; ++i) {
			cerr << low[i] << " ";
		}
		cerr << "\n";
	#endif

	// Ce inseamna ca un nod sa aiba low[i] == depth[i]?
	// 1. Nu face parte dintr-un ciclu sau este fix tatal unui ciclu

	// Hai sa aflam punctele critice / de articulare!

	dfs_critice(1, 0);

	#ifdef LOCAL
		cerr << "Punctele critice sunt: ";
		for (auto nod : puncte_critice) {
			cerr << nod << " ";
		}
		cerr << "\n";
	#endif

	// Hai sa gasim poduri!
	// Un pod este un nod intre 2 puncte critice
	// Dar mai mult de atat, muchia trebuie sa fie "rosie" de la tata la fiu
	// Trebuie si ca fiul sa nu aiba low mai mic sau egal decat depth-ul tatalui

	dfs_poduri(1, 0);

	#ifdef LOCAL
		cerr << "Podurile sunt: " << endl;
		for (auto pod : poduri) {
			cerr << pod.first << " " << pod.second << "\n";
		}
		cerr << "\n";
	#endif

	// Hai sa gasim biconexe!

	dfs_biconexe(1, 0);

	cout << biconexe_pe_noduri.size() << endl;

	for(auto comp_biconexa : biconexe_pe_noduri) {
		for(auto nod : comp_biconexa) {
			cout << nod << " ";
		}
		cout << "\n";
	}
}