Cod sursa(job #3177950)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 30 noiembrie 2023 17:41:53
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_map>

using namespace std;

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

const int N = 1e5 + 1;

int n, m, timp;

stack <int> s;

vector < vector <int> > bc, v(N);
vector <int> aux;
unordered_map<int, int> viz, tin, low;

void findbc(int nod, int parent)
{
	viz[nod] = 1;
	tin[nod] = ++timp;
	low[nod] = tin[nod];
	s.push(nod);
	for (auto& it : v[nod])
	{
		if (it == parent)
			continue;
		if (viz[it] == 1)
		{
			low[nod] = min(low[nod], tin[it]);
			continue;
		}
		findbc(it, nod);
		low[nod] = min(low[nod], low[it]);
		if (low[it] >= tin[nod])
		{
			aux.clear();
			while (!s.empty() && s.top() != nod)
			{
				aux.push_back(s.top());
				s.pop();
			}
			aux.push_back(nod);
			bc.push_back(aux);
		}
	}
}

void read_me()
{
	in >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int l1, l2;
		in >> l1 >> l2;
		v[l1].push_back(l2);
		v[l2].push_back(l1);
	}
}

int main()
{
	read_me();
	findbc(1, 0);
	out << bc.size() << '\n';
	for (auto i : bc)
	{
		for (auto j : i)
		{
			out << j << ' ';
		}
		out << '\n';
	}
}