Cod sursa(job #3329248)

Utilizator raulthestormIlie Raul Ionut raulthestorm Data 12 decembrie 2025 14:49:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 100001;

int N, M, nrCB,
    Niv[NMAX], Nma[NMAX],
    S[NMAX], vf;

vector<int> G[NMAX], CB[NMAX];
bool viz[NMAX];

ifstream f("biconex.in");
ofstream g("biconex.out");

void citire()
{
	int x, y;
	f >> N >> M;
	for(int i = 1; i <= M; ++i)
	{
		f >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void DFScb(int x, int tata)
{
	S[++vf] = x;
	viz[x] = 1;
	Niv[x] = Niv[tata] + 1;
	Nma[x] = Niv[x];
	for(const auto &y : G[x])
	{
		if(y == tata) continue;
		if(viz[y])
			Nma[x] = min(Nma[x], Niv[y]);
		else
		{
			DFScb(y, x);
			Nma[x] = min(Nma[x], Nma[y]);
			if(Niv[x] <= Nma[y])
			{
				++nrCB;
				while(S[vf] != y)
					CB[nrCB].push_back(S[vf--]);
				CB[nrCB].push_back(y);
				--vf;
				CB[nrCB].push_back(x);
			}
		}
	}
}

void afis()
{
	g << nrCB << '\n';
	for(int i = 1; i <= nrCB; ++i, g << '\n')
		for(const auto &x : CB[i])
			g << x << ' ';
}

int main()
{
	citire();
	DFScb(1, 0);
	afis();
	f.close();
	g.close();
	return 0;
}