Cod sursa(job #3352726)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 30 aprilie 2026 21:33:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.6 kb
//https://infoarena.ro/problema/biconex

//#ifdef _MSC_VER
//	#define _CRT_SECURE_NO_WARNINGS
//#elif  __GNUC__
//	#pragma GCC optimize("Ofast,unroll-loops,inline")
//	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#endif

//#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>
#include <utility>
#include <cstdint>
//#include <cstdio>
//#include <algorithm>
#include <vector>
//#include <array>
//#include <list>
//#include <forward_list>
//#include <string>
//#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
#include <stack>
//#include <map>
//#include <set>
//#include <unordered_map>
//#include <unordered_set>
//#include <limits>
//#include <climits>
//#include <iomanip>
//#include <tuple>
//#include <numeric>
//#include <chrono>
//#include <memory>

using namespace std;

using int64 = int64_t;
using uint64 = uint64_t;
using int32 = int32_t;
using uint32 = uint32_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define rfor(i, st, dr) for(auto i=(st); i<=(dr); ++i)
#define for0(i,n) for(auto i=0; i<(n); ++i)
#define rfor0(i,n) for(auto i=(n)-1; i>=0; --i)
#define for1(i,n) for(auto i=1; i<=(n); ++i)
#define rfor1(i,n) for(auto i=(n); i>=1; --i)
#define foreach(x,a) for(auto& x : a)
#define cforeach(x,a) for(const auto& x : a)
#define ft first
#define sd second
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

//#define int int64

ifstream fin("biconex.in");
ofstream fout("biconex.out");

//FILE* fin = fopen("", "r");
//FILE* fout = fopen("", "w");

const int NRMAX = 100000;

vector<vector<int>> rez;
vector<int>	gr[NRMAX + 5];
stack<int> st;

int low[NRMAX + 5], tmp[NRMAX + 5];
bool b[NRMAX + 5];
int timp = 0;

void dfs(int vf, int vfvf)
{
	//cout << vf << " ";
	++timp;
	tmp[vf] = low[vf] = timp;
	b[vf] = true; 

	for (int x : gr[vf])
	{
		if (x == vfvf) // daca muchie catre parinte
			continue;
			
		if (!b[x]) // nu mai am vizitat nodul x
		{
			st.push(x);
			dfs(x, vf);
			
			low[vf] = min(low[vf], low[x]);

			// dupa ce am revenit
			if (low[x] >= tmp[vf]) // formam o componenta biconexa
			{
				int* aux = new int[sz(st)];
				int idx = 0;
				
				// ne intorem
				while (st.top() != x) 
				{
					aux[idx++] = st.top();
					st.pop();
				}
				aux[idx++] = st.top();
				aux[idx++] = vf;
				st.pop();

				// adaugam nodurile din stiva in raspuns
				rez.push_back(vector<int>(aux, aux + idx));
				delete[] aux;
			}
		}
		else // am mai vizitat nodul x
			low[vf] = min(low[vf], tmp[x]); // am gasit un ciclu, deci actualizez low[vf]

	}
}

int32 main()
{
	//FASTIO;
	int n, m, i;

	fin >> n >> m;
	while(m--)
	{
		int x, y;
		fin >> x >> y;
		gr[x].push_back(y);
		gr[y].push_back(x);
	}

	//componente biconexe
	for (i = 1; i <= n; ++i)
		if (!b[i])
			dfs(i, 0);

	fout << sz(rez) << "\n";
	cforeach(it, rez)
	{
		cforeach(x, it)
			fout << x << " ";
		fendl;
	}

	return 0;
}

/*
	Cezar aici vorbeste singur, nu baga in seama :)
	daca ne uitam la el ca un arbore 
	daca luam reper un nod 
	daca facem dfs pe el atunci vom avea muchi care is parcurse si unele care nu va mai fi nevoie sa le parcurgem 
	(adica cele care duc catre un nod vizitat)
	daca nu e nevoie sa parcurgem o muchie insemna ca avem o componenta biconexa
*/