Cod sursa(job #2982816)

Utilizator NiffSniffCojocaru Calin Marcu NiffSniff Data 20 februarie 2023 22:06:18
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
string file = "biconex";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
const int N = 100001;
vector <int> L[N];
vector < vector<int> > comp;
bitset <N> viz;
int tin[N], tmin[N], t;

void dfs(int x, int anterior = 0)
{
	tmin[x] = tin[x] = ++t;
	for (int y : L[x])
	{
		if (y != anterior)
		{
			if (tmin[y] == 0)
				dfs(y,x);
			if (tmin[x] > tmin[y])
			{
				tmin[x] = tmin[y];
			}
		}
	}
}

void dfs_t(int x, vector <int> &c)
{
	c.push_back(x);
	viz[x] = 1;
	for (int y : L[x])
	{
		if (!viz[y])
		{
			if (tmin[x] != tmin[y])
			{
				vector <int> v = { x,y };
				comp.push_back(v);
				vector <int> s;
				dfs_t(y, s);
				if (s.size() > 1)
				{
					comp.push_back(s);
				}
			}
			else
			{
				dfs_t(y, c);
			}
		}
	}
}
int main()
{
	int n, m, x, y, c(0);
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y;
		L[x].push_back(y);
		L[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if (tmin[i] == 0)
		{
			t = 0;
			dfs(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			vector <int>v;
			dfs_t(i,v);
			comp.push_back(v);
		}
	}
	cout << comp.size();
	for (vector <int> v : comp)
	{
		cout << '\n';
		for (int nod : v)
			cout << nod << ' ';
	}
}