Cod sursa(job #1460683)

Utilizator petru.cehanCehan Petru petru.cehan Data 13 iulie 2015 15:45:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
// 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;
}