Cod sursa(job #2508092)

Utilizator HumikoPostu Alexandru Humiko Data 11 decembrie 2019 15:40:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <bitset>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

static const int NMAX = 1e5+5;

int depth[NMAX];
int minDepth[NMAX];

stack <int> s;

vector <int> graph[NMAX];
vector <int> biconnectedComp[NMAX];

int k;

void dfs (int vertex, int father) {
	depth[vertex] = depth[father]+1;
	minDepth[vertex] = depth[vertex];
	s.push(vertex);

	for ( auto x:graph[vertex] ) {
		if ( depth[x] ) {
			//Daca din vertex dau de un nod deja vizitat, imi recalculez minDepth pt vertex
			if ( x != father ) {
				minDepth[vertex] = min(depth[x], minDepth[vertex]);
			}
		}
		else {
			dfs(x, vertex);
			//Verific daca, facand dfs in continuare, pot ajunge la un nod aflat mai sus in arbore
			minDepth[vertex] = min(minDepth[vertex], minDepth[x]);
			//Verific daca cel mai de sus nod in care as putea ajunge din fiu folosind alte muchii se afla sub tata
			//Daca da, inseamna ca tatal (vertex) este punct de articulatie
			//=> Toate nodurile din stiva (pana in vertex) apartin aceleiasi componente biconexe
			if ( minDepth[x] >= depth[vertex] )  {
			//	cout<<"mindepth de "<<x<<" "<<minDepth[x]<<" "<<"depth de "<<vertex<<" "<<depth[vertex]<<'\n';
				++k;
				while ( s.top() != x ) {
					biconnectedComp[k].push_back(s.top());
					s.pop();
				}

				biconnectedComp[k].push_back(x);
				biconnectedComp[k].push_back(vertex);
				
				s.pop(); 
				//^Imi scot x-ul
				//^De observat ca vertex inca poate sa apartina altei componente biconexe
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin>>n>>m;

	for ( int i = 1; i <= m; ++i ) {
		int a, b;
		cin>>a>>b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	dfs(1, 0);

	cout<<k<<'\n';
	for ( int i = 1; i <= k; ++i ) {
		for ( auto x:biconnectedComp[i] ) {
			cout<<x<<" ";
		}
		cout<<'\n';
	}
}