Cod sursa(job #2576371)

Utilizator dragossofiaSofia Dragos dragossofia Data 6 martie 2020 18:49:45
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define Nmax 100000

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n , m , t , disc[Nmax] , low[Nmax] , nrc ;
vector <int> ad[ Nmax];;
vector <int> sol[Nmax];
vector <int> S ;
void read()
{
    fin >> n >> m ;
    int x , y ;
    for( int i = 1 ; i <= m ; i ++ )
    {
        fin >> x >> y ;
        //cout<<x<<" "<<y<<"\n";
        ad[ x ].push_back( y );
        ad[ y ].push_back( x );
    }
}

void dfs( int nod , int parent )
{
    disc[ nod ] = low[ nod ] = ++ t;
    int i , w ;
    for( i = 0 ; i < ad[ nod ].size() ; i++ )
    {
        w = ad[ nod ][ i ];
        if( w == parent )
            continue ;
        if( disc[ w ] )
            low[ nod ] = min( low [ nod] , low [ w ] );
        else
        {
            S.push_back( w ) ;
            dfs ( w , nod );
            low[ nod ] = min( low [ nod] , low [ w ] );

            if( low [ w ] >= disc[ nod ] )
            {
             nrc++ ;
             S.push_back( nod ) ;

             while( S.empty() == false && S.back() != w )
                {
                 sol[ nrc ].push_back( S.back());
                 S.pop_back();
                }
             if( S.empty() == false )
                {
                 sol[ nrc ].push_back( S.back());
                 S.pop_back();
                }
            }

        }
    }

}
int main()
{
    read();
    dfs( 1 , 0 );
    fout<<nrc<<"\n";
    int i,j;
    for( i = 1 ; i <= nrc ; i ++ )
        {
         for( j = 0 ; j < sol[i].size() ; j ++ )
                fout<<sol[i][j]<<" ";
         fout<<"\n";
        }
    return 0;
}