Cod sursa(job #3194575)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 18 ianuarie 2024 17:19:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.09 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 // LOCAL

const int nmax = 1e5 + 7;
vector<int> g[nmax];

int depth[nmax], low[nmax];
int ap[nmax];

stack<int> dfs_stack; // retine nodurile pe care le-am vizitat in DFS in 
// ordinea in care le-am vizitat pentru a ajunge la nodul curent
// !! nu retine toate nodurile vizitate, ci doar cele de pe un anumit lant
// de la radacina pana la nodul curent

vector<vector<int>> comp_biconexe;

void dfs(int node, int parent, int adancime) {
	// cerr << "Called DFS with " << node << " " << parent << " " << adancime << "\n";

	// Adaugam nodul curent in stiva
	dfs_stack.push(node);

	depth[node] = low[node] = adancime;
	bool este_punct_de_articulatie = false;
	int nr_fii = 0;

	for(auto vec : g[node]) {
		if (vec == parent)
			continue; // cazul cand m-as intoarce la parinte dar nu am muchie de "back" catre parinte

		if (depth[vec] == -1) { // cazul cand merg intr-un nod nevizitat, deci imi este fiu si are muchie verde
			++nr_fii;

			dfs(vec, node, adancime + 1);
			low[node] = min(low[node], low[vec]);

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

				// Pe langa faptul ca ap[node] = true, mai stim si ca 
				// de la fiul vec in jos avem o componenta biconexa separata
				// pe care o putem extrage folosind informatia din stack

				vector<int> comp_curent;

				while(dfs_stack.top() != vec) {
					comp_curent.push_back(dfs_stack.top());
					dfs_stack.pop();
				}

				comp_curent.push_back(dfs_stack.top());
				dfs_stack.pop();

				comp_curent.push_back(node); // il adaug "din burta" fiindca node, fiind punct de articulatie,
				// poate aparea si in alte componente biconexe
				// deci nu il pot scoate din stack

				comp_biconexe.push_back(comp_curent);
			}
		} else { // cazul cand merg intr-un nod vizitat, deci imi este parinte si are muchie rosie
			low[node] = min(low[node], depth[vec]);
		}
	}

	// cerr << node << " " << depth[node] << " " << low[node] << "\n";
	// cerr << "nr_fii = " << nr_fii << "\n";
	// cerr << "este_punct_de_articulatie = " << este_punct_de_articulatie << "\n";

	// Un nod este punct de articulatie daca are un fiu vec astfel incat low[vec] >= depth[node]

	if ( adancime > 0 /* nu suntem in radacina */ && este_punct_de_articulatie )
		ap[node] = true;

	// Si mai avem caz special pentru radacina
	if ( adancime == 0 && nr_fii >= 2 ) 
		ap[node] = true; 
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for(int i = 0; i < nmax; i++) {
		depth[i] = -1;
		low[i] = -1;
	}

	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, 1, 0);

	// Afisam punctele de articulatie
	#ifdef LOCAL
		for(int i = 1; i <= n; i++) {
			if(ap[i] == true) {
				cerr << i << " este punct de articulatie\n";
			}
		}
	#endif // LOCAL

	// Afisam componentele biconexe
	cout << comp_biconexe.size() << "\n";
	for(auto comp : comp_biconexe) {
		for(auto nod : comp) {
			cout << nod << " ";
		}
		cout << "\n";
	}
}