Cod sursa(job #2944055)

Utilizator mati.coldea@gmail.comMatei Coldea [email protected] Data 21 noiembrie 2022 23:11:14
Problema Componente biconexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[10000];
vector<int> viz(10000,0);

int n, m;


vector<int> low(10000);
vector<int> nivel(1000);

stack<int> s;// in stiva salvez elementele pe masura ce le parcurg
// in aceasta stiva se vor regasi componentele conexe sub forma de ciclu, scot din stiva pana dau de k



//mod de functionare
// creez un sir de nivel, in care salvez nivelul la care se afla fiecare nod, in dfs tree
// creez un alt sir, low, in care salvez nivelul cel mai mic accesibil din acel nod, mergand in jos(la vecinii lui care nu coincid cu tatal)
// in momentul in care dintr-un nod cu nivel x putem ajunge la un nivel mai mic decat x, atunci inseamna ca am o muchie de intoarcere
//deci am un ciclu
// componenta biconexa este un un ciclu sau o muchie (trebuie sa aiba minim 2 noduri)
// in momentul in care am doua noduri care nu se afla in acelasi componenta conexa(nu pot ajunge la acelasi nivel)
// inseamna ca am o muchie critica care leaga cele doua componente si nodul cu nivelul cel mai de sus este punctul de articulatie
//

vector<vector<int>> rez(1000);
int nr = 1;
void dfs(int k, int tata) {
	viz[k] = 1;
	nivel[k] = nivel[tata] + 1;
	low[k] = nivel[k];
	s.push(k);

	for (auto i : g[k]) {
		if (i != tata) {
			if (viz[i] == 1) {
				if (low[k] > nivel[i]) {
					low[k] = nivel[i];
				}
			}
			else {
				dfs(i, k);
				if (low[k] > low[i]) {// reactualizarea pe apelul de dinainte
					low[k] = low[i];
				}



				//// punctul de articulatie leaga o muchie critica de un ciclu
				//// muchiile critice sunt muchiile care leaga ciclurile
				//if (nivel[k] <= low[i] && k!=1) {// punct de articulatie
				////daca am ajuns intr-un punct in care am valoarea low a fiului mai mare ca nivelul tatalui
				//// adica cele doua noduri nu fac parte din acelasi ciclu 
				////k!=1 pentru a nu lua in considerare radacina
				//	cout << k << ' ';
				//}


				//if (nivel[k] < low[i]) {// muchie critica
				//// nu mai avem nivel[k] <= low[i] pentru ca nu putem avea o muchie cu o singura coordonata
				//	cout << k << '-' << i << '\n';
				//}


				//// la fel atunci cand 
				//// daca o componenta nu contine nici-un punct de articulatie
				//// punctele de articulatie fac parte din componente biconexe


				if (nivel[k] <= low[i]) {// scriere componente biconexe
					
					while (s.top() != i) {
						//cout << s.top()<<' ';
						rez[nr].push_back(s.top());
						s.pop();
					}
					//cout << i << ' ';
					rez[nr].push_back(i);

					s.pop();
					//cout << k << '\n';
					rez[nr].push_back(k);
					nr++;
				}

			}

		}
	}

}



int main() {

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

	
	fout << nr-1 << '\n';
	for (int i = 1; i <= nr-1; i++) {
		for (auto j : rez[i]) {
			fout << j << ' ';
		}
		fout << '\n';
	}


	

}