Cod sursa(job #772172)

Utilizator danalex97Dan H Alexandru danalex97 Data 28 iulie 2012 16:18:09
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
// Un graf biconex este un graf conex din care , 
// dupa ce taiem orice punct ramane tot conex.
// Pentru a afla componentele biconexe trebuie 
// sa determinam punctele de articulatie.
// Un punct de articulatie este format din *muchii*
// ( deci un punct de articulatie se afla in mai multe componente )
// Folosim o stiva si in momentul cand in arborele DFS ajungem la 
// un nod fara fii cautam drumuri de intoarecere. Drumul de intoarcere 
// cu nodul cel mai sus determina componenta biconexa.
// In cazul in care nu avem drumuri de intaorcere din punct ,
// componenta e formata din nod si predecesorul sau.

#include <fstream>
#include <vector>
using namespace std;

ifstream F("biconex.in");
ofstream G("biconex.out");

#define Nmax 100011
#define Mmax 200011

typedef vector<int>::iterator Iter;

vector < int > Rez[Nmax]; 
vector < int > Leg[Nmax];
vector < int > Stiva;

int Marked[Nmax];
int Turn[Nmax];
int N,M,Co,Return=1<<30;

void Get( int Nod,int Start,int Step )
{
	Marked[Nod]=1;
	Turn[Nod]=Step;
	Stiva.push_back( Nod );
	
	for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
	{
		if ( Turn[Nod] > Return ) return;
			else Return=1<<30;
		if ( !Marked[ *it ] )
			Get( *it , Start ,Step+1 );
	}
	
	if ( Turn[Nod] > Return ) return;
		else Return=1<<30;
	
	if ( Nod!=Start )
	{
		int Lvl=0;
		for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
			if ( Step - Turn[*it] > Lvl )
				Lvl=Step - Turn[*it];
		Return=Step - Lvl;
		
		++Co;
		while ( Lvl )
		{
			Rez[Co].push_back( Stiva.back() );
			Stiva.pop_back();
			--Lvl;
		}
		Rez[Co].push_back( Stiva.back() );
	}
}

int main()
{
	F>>N>>M;
	for (int x,y;M;--M)
	{
		F>>x>>y;
		Leg[x].push_back( y );
		Leg[y].push_back( x );
	}
	
	for (int i=1;i<=N;++i)
		if ( !Marked[i] )
		{
			Get( i , i , 0);
			while ( Stiva.size() ) 
				Stiva.pop_back();
		}
	
	G<<Co<<'\n';
	for (int i=1;i<=Co;++i)
	{
		for ( Iter it=Rez[i].end();it!=Rez[i].begin();--it )
			G<< *(it-1) <<' ';
		G<<'\n';
	}
}