Cod sursa(job #772200)

Utilizator danalex97Dan H Alexandru danalex97 Data 28 iulie 2012 18:42:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 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 sau muchiile critice.
// Un punct de articulatie este format din *muchii*
// ( deci un punct de articulatie se afla in mai multe componente )
// Punctele de articulatie se mai numesc si pnct. critice.
// Un pnct. este critic , daca si numai daca de la cel putin un fiu
// al sau se poate ajunge mai sus in arbore decat la punctul respectiv.
// O muchie este critica daca este nivelul minim accesibil al nodului de mai jos
// este mai mic decat cel al tatului in arborele DFS.

// Parcurgem arborele DFS si atunci cand avem un nod care nu poate ajunge mai sus 
// de tata am gasit o componenta conexa. Acest nod a fost unul de legatura.

#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];
int StivaX[Nmax], StivaY[Nmax], L;

int Marked[Nmax];
int Mark[Nmax];
int Best[Nmax];
int Niv[Nmax];
int Dad[Nmax];

int N,M,Co;

void Get( int Nod )
{
	Marked[Nod]=1;
	Best[Nod]=Niv[Nod];
	
	for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
		if ( !Marked[ *it ] )
		{
			Niv[ *it ] = Niv[Nod] + 1;
			Dad[ *it ] = Nod ;
			
			StivaX[++L]=Nod;
			StivaY[L]= *it ;
			Get( *it );
			
			Best[Nod] = min( Best[Nod] , Best[ *it ] );
			
			if ( Best[ *it ] >= Niv[ Nod ] )
			{
				++Co;
				
				for ( ; L >= 0 && ( StivaX[L+1] != Nod || StivaY[L+1] != *it ); L--  )
				{
					if ( Mark[ StivaY[L] ] != Co )
					{
						Mark[ StivaY[L] ] = Co;
						Rez[Co].push_back( StivaY[L] );
					}
					if ( Mark[ StivaX[L] ] != Co )
					{
						Mark[ StivaX[L] ] = Co;
						Rez[Co].push_back( StivaX[L] );
					}
				}
			}
		}	
		else 
			if ( *it != Dad[ Nod ] ) 
				Best[Nod] = min( Best[Nod], Niv[ *it ] );
}

int main()
{
	F>>N>>M;
	for (int x,y;M;--M)
	{
		F>>x>>y;
		Leg[x].push_back( y );
		Leg[y].push_back( x );
	}
	
	Get( 1 );
	
	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';
	}
}