Cod sursa(job #522577)

Utilizator invatacelTudorache Marius invatacel Data 15 ianuarie 2011 15:18:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int n,m;

vector<int> V[1<<17];
vector<vector<int> > C;
stack<int> ST;

int minh[1<<17];
int H[1<<17];

void pop_comp(int x, int tat)
{
	vector<int> comp;

	while (ST.size() > 0 && ST.top() != x)
	{
		comp.push_back(ST.top());
		ST.pop();
	}

	if (ST.size() > 0)
	{
		comp.push_back(ST.top());
		ST.pop();
	}
	
	if (tat != -1) comp.push_back(tat);

	C.push_back(comp);
}

void df(int x,int tat)
{
	ST.push(x);
	
	for (size_t i=0;i<V[x].size();i++)
		if (!H[V[x][i]])
		{
			H[V[x][i]] = H[x] + 1;
			df(V[x][i],x);
			if (minh[V[x][i]] < minh[x]) minh[x] = minh[V[x][i]];
		}
		else
		{
			if (H[V[x][i]] < minh[x]) minh[x] = H[V[x][i]];
		}

	if (tat != -1 && minh[x] == H[tat])
		pop_comp(x,tat);
}

int main()
{
	freopen ("biconex.in","r",stdin);
	freopen ("biconex.out","w",stdout);

	scanf ("%d%d",&n,&m);
	memset(minh,1,sizeof(minh));

	for (;m;m--)
	{
		int a,b;
		scanf ("%d%d",&a,&b);
		V[a].push_back(b);
		V[b].push_back(a);
	}

	for (int i=1;i<=n;i++)
		if (!H[i])
		{
			H[i] = 1;

			df(i,-1);
		}

	printf ("%d\n",C.size());
	for (size_t i=0;i<C.size();i++)
	{
		for (size_t j=0;j<C[i].size();j++)
			printf ("%d ",C[i][j]);
		printf ("\n");
	}

	return 0;
}