Cod sursa(job #1428234)

Utilizator radudorosRadu Doros radudoros Data 3 mai 2015 22:32:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<algorithm>

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

vector<int> v[100001];
bitset<100001> viz;
int low[100001];
int tata[100001];
int dft[100001];
vector<int> st;
vector<vector<int>> sol;

int cnt = 0;

void get_sol(int x, int y)
{
	vector<int> aux;
	sol.push_back(aux);
	while (st.back()!=y)
	{
		sol[sol.size() - 1].push_back(st.back());
		st.pop_back();
	}
	st.pop_back();
	sol[sol.size() - 1].push_back(x);
	sol[sol.size() - 1].push_back(y);
}

void dfs(int x,int f)
{
	dft[x] = low[x] = ++cnt;
	for (auto it : v[x])
	{
		if (it != f)
		{
			if (!dft[it])
			{
				st.push_back(it);
				dfs(it, x);

				low[x] = min(low[it], low[x]);
				if (low[it] >= dft[x])
					get_sol(x, it);
			}
			else
			{
				low[x] = min(low[x], dft[it]);
			}
		}
	}
}



int main()
{
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);

	fout << sol.size() << '\n';
	for (int i = 0; i < sol.size(); i++)
	{
		for (int j = 0; j < sol[i].size(); j++)
		{
			fout << sol[i][j] << ' ';
		}
		fout << '\n';
	}
}