Pagini recente » Cod sursa (job #3224670) | Cod sursa (job #3191608) | Cod sursa (job #1274385) | Cod sursa (job #1233480) | Cod sursa (job #1460683)
// Numarul Componentelor Biconexe
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in") ;
ofstream fout ("biconex.out") ;
struct nod
{
int info ;
nod * next ;
} ;
nod * L [100001] ;
int N , M ;
void Add ( int i , int j ) ;
void Citire()
{
fin >> N >> M ;
int a , b ;
while ( M >= 1 )
{
fin >> a >> b ;
Add ( a , b ) ;
-- M ;
}
}
void Add ( int i , int j )
{
nod * p = new nod ;
p->info = j ;
p->next = L [i] ;
L [i] = p ;
p = new nod ;
p->info = i ;
p->next = L [j] ;
L [j] = p ;
}
bool viz [100005] ;
int niv [100005] , low [100005] ;
stack < int > stiva ;
vector < int> bic [100005] ;
int nr_comp ;
void AdaugaCompBiconexa ( int nd , int fiu )
{
++ nr_comp ;
while ( stiva.top() != fiu )
bic [ nr_comp ].push_back ( stiva.top () ) , stiva.pop () ;
stiva.pop () ; // scot si fiul
bic [ nr_comp ].push_back ( nd ) , bic [ nr_comp ].push_back ( fiu ) ;
}
void DFS ( int nd , int parinte )
{
viz [ nd ] = 1 ;
niv [ nd ] = low [ nd ] = niv [ parinte ] + 1 ;
for ( nod * p = L [ nd ] ; p != 0 ; p = p->next )
{
if ( p->info == parinte )
continue ;
if ( viz [ p->info ] == 1 )
low [ nd ] = min ( low [ nd ] , niv [ p->info ] ) ;
else
{
stiva.push ( p->info ) ;
DFS ( p->info , nd ) ;
low [ nd ] = min ( low [ nd ] , low [ p->info ] ) ;
if ( low [ p->info ] >= niv [ nd ] )
AdaugaCompBiconexa ( nd , p->info ) ;
}
}
}
#
int main()
{
Citire () ;
for ( int i = 1 ; i <= N ; ++ i )
if ( viz [i] == 0 )
DFS ( i , 0 ) ;
fout << nr_comp << "\n" ;
for ( int i = 1 ; i <= nr_comp ; ++ i )
{
for ( unsigned int j = 0 ; j < bic [ i ].size() ; ++ j )
fout << bic [ i ] [ j ] << " " ;
fout << "\n" ;
}
return 0;
}