Cod sursa(job #3325764)

Utilizator adelinapetreAdelina Petre adelinapetre Data 26 noiembrie 2025 13:13:31
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int Nmax = 1e5 + 5;

vector<int> g[Nmax];
int vis[Nmax], depth[Nmax], low[Nmax];
stack<pair<int, int>> st;
vector<int> bicomp[3 * Nmax];

int cntcomp = 0;

void dfs(int nod, int par)
{
	depth[nod] = depth[par] + 1;
	low[nod] = depth[nod];
	vis[nod] = 1;
	int cnt = 0;
	for (auto it : g[nod])
	{
		if (vis[it] == 0)
		{
			cnt++;
			st.push({ nod, it });
			dfs(it, nod);
			low[nod] = min(low[nod], low[it]);
			if ((low[it] >= depth[nod]) || (nod == 1 && cnt > 1))//NOD e  pct de articulatie
			{
				cntcomp++;
				bicomp[cntcomp].push_back(nod);
				bicomp[cntcomp].push_back(it);
				while (st.top().first != nod && st.top().second != it)
					bicomp[cntcomp].push_back(st.top().second), st.pop();
				st.pop();
			}
		}
		else if(it != par)
			low[nod] = min(low[nod], low[it]);
	}

}

int main()
{
	int n, m, x, y;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);
	cout << cntcomp << '\n';
	for (int i = 1; i <= cntcomp; i++)
	{
		for (auto it : bicomp[i])
			cout << it << " ";
		cout << '\n';
	}
}