Cod sursa(job #3369321)

Utilizator batasAndrei Batis batas Data 19 octombrie 2026 18:02:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;

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

int n, m;
int idx;
VVI G, cbc;
VI t, index, low;
stack<int> stk;

void ReadInput();
void DFS(int node);
void Solve();
void AddComp(int node, int target);

int main()
{
	ReadInput();
	Solve();
	
	return 0;
}

void Solve()
{
	for (int node = 1; node <= n; ++node)
		if (!index[node])
			DFS(node);
			
	fout << cbc.size() << '\n';
			
	for (auto comp : cbc)
	{
		for (int node : comp)
			fout << node << ' ';
		fout << '\n';
	}
}

void DFS(int node)
{
	index[node] = low[node] = ++idx;
	stk.push(node);
	
	for (int nbr : G[node])
	{
		if (t[node] == nbr)
			continue;
			
		if (!index[nbr])
		{
			DFS(nbr);
			low[node] = min(low[node], low[nbr]);
			
			if (low[nbr] >= index[node])
				AddComp(node, nbr);
		}
		else
			low[node] = min(low[node], index[nbr]);
	}
}

void AddComp(int node, int target)
{
	VI comp;
	int next;
	do
	{
		next = stk.top();
		stk.pop();
		
		comp.push_back(next);
		
	} while (next != target);
	
	comp.push_back(node);
	cbc.push_back(comp);
}

void ReadInput()
{
	fin >> n >> m;
	
	G = VVI(n + 1);
	t = index = low = VI(n + 1);
	
	int u, v;
	while (m--)
	{
		fin >> u >> v;
		
		G[u].push_back(v);
		G[v].push_back(u);
	}
}