Cod sursa(job #936844)

Utilizator superman_01Avramescu Cristian superman_01 Data 8 aprilie 2013 22:08:13
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb

#include<fstream>
#include<vector>
#include<stack>


#define NMAX 100005
#define pb push_back
#define forit(it, v) for( it = (v).begin(); it != (v).end(); ++ it)
#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,numb;
vector <int> graph[NMAX],solution[NMAX];
stack <int> Stack;
int Level[NMAX],Low[NMAX];

void read( void )
{
	f>>n>>m;
	for(int i(1) ; i <= m ; ++i )
	{
		int x,y;
		f>>x>>y;
		graph[x].pb(y);
		graph[y].pb(x);
	}
	
	f.close();
}

void ClearTheStack ( int x , int  y )
{
	while( Stack.top() != y )
	{
		solution[numb].pb(Stack.top());
		Stack.pop();
	}
	solution[numb].pb(y);
	solution[numb++].pb(x);
	Stack.pop();	
}
void DepthFirstSearch( int Son , int Father  )
{
	vector <int> ::iterator it;
	Low[Son]=Level[Son];
	forit(it,graph[Son])
	{
		   if( *it == Father ) continue;
	
		   if( !Level[*it] )
	   {
		   Level[*it]=Level[Son]+1; 
		    DepthFirstSearch(*it,Son);
		    Low[Son]= min ( Low[Son],Low[*it] );
          if ( Low[ *it ] >= Level[Son] )
             ClearTheStack( Son , *it );			  
		}
		   else
			   Low[Son]=min ( Low[Son] ,Low[ *it ] );
	}

}
void write ( void )
{
	vector <int> ::iterator it;
	g<<numb<<"\n";
	for(int i(0); i < numb; ++i )
	{
		forit(it,solution[numb])
			g<<*it<<" ";
		g<<"\n";		
	}
	g.close();
}
int main( void )
{
	read();
	Stack.push(1);
	DepthFirstSearch(1,0);
	write();
	return 0;	
}