Pagini recente » Istoria paginii runda/concursdeholboca | Cod sursa (job #286314) | Cod sursa (job #1244519) | Istoria paginii runda/23456346564 | Cod sursa (job #856544)
Cod sursa(job #856544)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define nmax 100001
using namespace std ;
struct muchie
{
int x , y ;
}stiva [ nmax ] , var ;
int N , M , stiva_nr , nr_componente ;
vector<int> vecini [ nmax ] , biconexe [ nmax ] ;
int t [ nmax ] , niv [ nmax ] , l [ nmax ] ;
bool vizitat [ nmax ] ;
void citire ()
{
FILE *fin ;
fin = fopen ( "biconex.in" , "rt" ) ;
fscanf ( fin , "%d %d" , &N , &M ) ;
for ( int i = 1 ; i <= M ; i++ )
{
int a , b ;
fscanf ( fin , "%d %d" , &a , &b ) ;
vecini [ a ].push_back ( b ) ;
vecini [ b ].push_back ( a ) ;
}
l [ 1 ] = 1 ;
t [ 1 ] = 0 ;
niv [ 1 ] = 1 ;
}
void stiva_adauga ( muchie aaa )
{
stiva_nr++ ;
stiva [ stiva_nr ] = aaa ;
}
void gasit_componenta ( int nod )
{
nr_componente++ ;
do
{
biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].x ) ;
biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].y ) ;
stiva_nr-- ;
}while ( stiva [ stiva_nr + 1 ].x != nod && stiva [ stiva_nr + 1 ].y !=nod ) ;
}
void dfs ( int nod )
{
vizitat [ nod ] = 1 ;
for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
{
int y = vecini [ nod ][ i ] ;
if ( vizitat [ y ] )
{
if ( y != t [ nod ] )
{
if ( l [ nod ] > l [ y ] ) l [ nod ] = niv [ y ] ;
}
continue ;
}
t [ y ] = nod ;
niv [ y ] = niv [ nod ] + 1 ;
l [ y ] = niv [ y ] ;
var.x = nod , var.y = y ;
stiva_adauga ( var ) ;
dfs ( y ) ;
if ( l [ nod ] > l [ y ] ) l [ nod ] = l [ y ] ;
if ( l [ y ] >= niv [ nod ] ) gasit_componenta ( nod ) ;
}
}
int main ()
{
citire () ;
for ( int i = 1 ; i <= N ; i++ )
if ( !vizitat [ i ] )
{
niv [ i ] = 1 ;
t [ i ] = 0 ;
dfs ( i ) ;
if ( stiva_nr ) nr_componente++ ;
while ( stiva_nr )
{
biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].x ) ;
biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].y ) ;
stiva_nr--;
}
}
FILE *fout ;
fout = fopen ( "biconex.out" , "wt" ) ;
fprintf ( fout , "%d\n" , nr_componente ) ;
for ( int i = 1 ; i <= nr_componente ; i++ )
{
sort ( biconexe [ i ].begin () , biconexe [ i ].end () );
for ( int j = 0 ; j < biconexe [ i ].size() ; j++ )
if ( biconexe [ i ][ j ] != biconexe [ i ][ j + 1 ] )
fprintf ( fout , "%d " , biconexe[i][j] ) ;
fprintf ( fout , "\n" ) ;
}
fclose ( fout ) ;
return 0 ;
}