Cod sursa(job #2570637)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 4 martie 2020 18:12:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e5 + 1;

vector <int> adj[DIM];
vector <vector <int> > ans;

int stiva[DIM];
int best[DIM];
int found[DIM];
int it;

void dfs(int nod)
{
	stiva[++it] = nod;
	
	for(auto i : adj[nod])
		if(found[i])
		{
			best[nod] = min(best[nod], found[i]);
		}
		else
		{
			int pos = it;
			found[i] = best[i] = found[nod] + 1;
			dfs(i);
			best[nod] = min(best[nod], best[i]);
			
			if(best[i] >= found[nod])
			{
				ans.emplace_back();
				ans.back().emplace_back(nod);
				
				while(it > pos)
				{
					ans.back().emplace_back(stiva[it--]);
				}
			}
		}
}

main()
{
	int n, m;
	fin >> n >> m;
	
	for(; m; --m)
	{
		int x, y;
		fin >> x >> y;
		
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);
	}
	
	dfs(1);
	
	fout << ans.size() << '\n';
	
	for(auto i : ans)
	{
		for(auto j : i)
			fout << j << ' ';
		
		fout << '\n';
	}
}