Cod sursa(job #717922)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 20 martie 2012 12:28:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<fstream>
#include<vector>
#include<stack>

#define mp make_pair
#define pb push_back
#define INfile "biconex.in"
#define OUTfile "biconex.out"
#define  NMAX 100009

using namespace std;

ifstream F ( INfile ) ;
ofstream G ( OUTfile ) ;

vector < int > V [ NMAX ] , SOL [ NMAX ] ;
stack < pair < int , int > > S ;

int N , M , cmp ;
int lvl [ NMAX ] , lwr [ NMAX ] ; 

void solve () ;
void write () ;
void DFS ( int dad , int ante ) ;
void read () ;

int main ()
{
	read () ;
	
	solve () ;
	
	write () ;
	
	F.close () ;
	G.close () ;
	
	return 0 ;
}

void read () 
{
	int i , x , y ;
	F >> N >> M ;
	for ( i = 1 ; i <= M ; ++ i )
	{
		F >> x >> y ;
		V [ x ].pb ( y ) ;
		V [ y ].pb ( x ) ;
	}
}


void solve () 
{
	int i ;
	
	for ( i = 1 ; i <= N ; ++ i ) 
		lwr [ i ] = 1 << 30 ;
	
	for ( i = 1 ; i <= N ; ++ i )
		if ( ! lvl [ i ] )
		{
			lvl [ i ] = 1 ;
			//S.push ( i ) ;
			DFS ( i , 0 ) ;
		}
}

void DFS ( int dad , int ante ) 
{
	
	int i , son ;
	for ( i = V [ dad ].size () - 1 ; i > -1 ; -- i )
	{
		
		son = V [ dad ][ i ] ;
		if ( son == ante ) continue ;
		if ( ! lvl [ son ] )
		{
			lvl [ son ] = lvl [ dad ] + 1 ;
			S.push ( mp ( dad , son ) ) ;
			DFS ( son , dad ) ;
			if ( lwr [ son ] < lwr [ dad ] )
				lwr [ dad ] = lwr [ son ] ;
			if ( lwr [ son ] >= lvl [ dad ] ) 
			{
				++ cmp ;
				while ( S.top ().first != dad || S.top ().second != son ) 
				{
					SOL [ cmp ].pb ( S.top ().second ) ;
					S.pop () ;
				} 
				S.pop () ;
				SOL [ cmp ].pb ( son ) ;
				SOL [ cmp ].pb ( dad ) ;
			}
		}
		else 
			if ( lvl [ son ] < lwr [ dad ] )
				lwr [ dad ] = lvl [ son ] ;
	}
}

void write () 
{
	int i , j ;
	G << cmp << '\n' ;
	for ( i = 1 ; i <= cmp ; ++ i )
	{
		for ( j = SOL [ i ].size () - 1 ; j > -1 ; -- j )
			G << SOL [ i ][ j ] << ' ' ;
		G << '\n' ;
	}
}