Cod sursa(job #662190)

Utilizator JBaccountCatalin JBaccount Data 16 ianuarie 2012 02:00:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define NM 100005
#define PB push_back

vector <int> G[NM], B[NM];

int N, M, Bdim, viz[NM], L[NM], how_high[NM], stiva[NM], stivadim;

void adauga(int nod)
{
	++Bdim;
	while (stiva[stivadim] != nod)
	{
		B[Bdim].PB(stiva[stivadim]);
		--stivadim;
	}	
	B[Bdim].PB(nod);
	--stivadim;
}

void dfs(int nod, int fat)
{
	viz[nod] = 1;
	stiva[++stivadim] = nod;
	L[nod] = L[fat] + 1;
	how_high[nod] = L[nod];
	int mlev = L[nod];
	
	for (int i = 0; i < G[nod].size(); ++i)
	{
		int nnod = G[nod][i];
		if (viz[nnod]) 
		{
			mlev = min(mlev, L[nnod]);
			continue;
		}	
		dfs(nnod, nod);
		how_high[nod] = min(how_high[nod], how_high[nnod]);
		if (how_high[nnod] < L[nod]) continue;
		adauga(nnod);
		B[Bdim].PB(nod);
	}	
	how_high[nod] = min(how_high[nod], mlev);
}

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