Cod sursa(job #669916)

Utilizator JBaccountCatalin JBaccount Data 27 ianuarie 2012 22:58:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NM 100005

int N, M, Bdim, L[NM], HH[NM], viz[NM], stack[NM];
vector <int> G[NM], B[NM];

void es (int nod)
{
	++Bdim;
	while (stack[stack[0]] != nod)
	{
		B[Bdim].push_back(stack[stack[0]]);
		--stack[0];
	}	
	--stack[0];
	B[Bdim].push_back(nod);
}

void df (int nod, int fat)
{
	L[nod] = L[fat] + 1;
	HH[nod] = L[nod];
	viz[nod] = 1;
	stack[++stack[0]] = nod;
	
	for (int i = 0; i < G[nod].size(); ++i)
	{
		int nnod = G[nod][i];
		if (viz[nnod])
		{
			HH[nod] = min(HH[nod], L[nnod]);
			continue;
		}	
		df (nnod, nod);
		HH[nod] = min(HH[nod], HH[nnod]);
		if (HH[nnod] < L[nod]) continue;
		es(nnod);
		B[Bdim].push_back(nod);
	}	
}

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);
	}	
	
	df (1, 0);
	
	printf ("%d\n", Bdim);
	
	for (int i = 1; i <= Bdim; ++i)
	{
		//printf ("%d\n", B[i].size());
		for (int j = 0; j < B[i].size(); ++j) printf ("%d ", B[i][j]);
		printf ("\n");
	}	
	
	return 0;
}