Cod sursa(job #1923350)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2017 22:54:47
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );

stack< pair<int,int> > st;
vector< int > G[ 100010 ] , sol[100010];
int idx[100010],mini[100010],ans,a,b,x,y,n,m,i;

void DF( int nod, int parinte )
{
    idx[ nod ] = idx[ parinte ] + 1;
    mini[ nod ] = idx[ nod ];
    for( auto it : G[ nod ] )
    {
        if( it != parinte )
        {
            if( !idx[ it ] )
            {
                st.push( {nod,it} );
                DF( it , nod );

                if( mini[ it ] >= idx[ nod ] )
                {
                    ++ans;
                    a = 0;
                    b = 0;
                    do
                    {
                        a = st.top().f;
                        b = st.top().s;
                        st.pop();
                        sol[ ans ].push_back( b );
                    }while( a != nod && b != it );
                    sol[ ans ].push_back( a );
                }
            }
            mini[ nod ] = min( mini[ nod ] , mini[ it ] );
        }
    }
}

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }

    DF( 1 , 0 );

    fout<<ans<<'\n';
    for( i = 1 ; i <= ans ; i++ )
    {
        for( auto it : sol[ i ] )
            fout<<it<<' ';
        fout<<'\n';
    }

return 0;
}