Cod sursa(job #3307136)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 18 august 2025 11:49:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
vector <int> v[100005], stiva;
int h[100005], min_h[100005];
vector <vector <int>> ras;
void dfs( int x ){
	int i, y;
	stiva.push_back( x );
	min_h[x] = h[x];
	//cout << x << ' ' << h[x] << '\n';
	for( i = 0; i < v[x].size(); i++ ){
		y = v[x][i];
		//cout << y << ' ' << h[y] << '\n';
		if( h[y] == 0 ){
			h[y] = h[x] + 1;
			dfs( y );
			min_h[x] = min( min_h[y], min_h[x] );
			if( min_h[y] >= h[x] ){
				vector <int> comp;
				while( stiva.back() != y ){
					comp.push_back( stiva.back() );
					stiva.pop_back();
				}
				comp.push_back( y );
				stiva.pop_back();
				comp.push_back( x );
				ras.push_back( comp );
			}
		}
		else{
			min_h[x] = min( h[y], min_h[x] );
		}
	}
}
int main(){
	int n, m, i, j, x, y;
	ifstream fin( "biconex.in" );
	ofstream fout( "biconex.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y;
		v[x].push_back( y );
		v[y].push_back( x );
	}
	h[1] = 1;
	dfs( 1 );
	fout << ras.size() << '\n';
	for( i = 0; i < ras.size(); i++ ){
		for( j = 0; j < ras[i].size(); j++ ){
			fout << ras[i][j] << ' ';
		}
		fout << '\n';
	}
	return 0;
}