Cod sursa(job #1216173)

Utilizator pulseOvidiu Giorgi pulse Data 3 august 2014 16:23:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 100005

using namespace std;

int n, m, ksol, Depth[nmax], Low[nmax];
vector <int> G[nmax], sol[nmax], st;

void Biconex(int node, int son)
{
	++ksol;
	while (st.back() != son)
	{
		sol[ksol].push_back(st.back());
		st.pop_back();
	}
	sol[ksol].push_back(node);
	sol[ksol].push_back(son);
	st.pop_back();
}

void DFS(int node, int depth, int father)
{
	Depth[node] = depth;
	Low[node] = depth;
	for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
	{
		int x = *it;
		if (*it == father) continue;
		if (!Depth[*it])
		{
			st.push_back(*it);
			DFS(x, depth + 1, node);
			if (Low[*it] >= Depth[node]) Biconex(node, *it);
			Low[node] = min(Low[node], Low[*it]);
		}
		Low[node] = min(Low[node], Depth[*it]);
	}
}

int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	DFS(1, 1, 0);
	printf("%d\n", ksol);
	for (int i = 1; i <= ksol; ++i)
	{
		sort(sol[i].begin(), sol[i].end());
		for (vector <int> :: iterator it = sol[i].begin(); it != sol[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
	return 0;
}