Cod sursa(job #2133353)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 16 februarie 2018 20:37:38
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stack>
#include <vector>
#include <fstream>
#define nmax 100005
#define x first
#define y second
using namespace std;
ofstream fout ("biconex.out");
ifstream fin ("biconex.in");
int nivel[nmax],intorc[nmax],a,b,crt,i,n,m;
stack < pair < int , int > > q;
vector < int > w[nmax],ans[nmax];
void dfs( int nod , int parinte )
{
    nivel[ nod ] = intorc[ nod ] = nivel[ parinte ] + 1;
    ///cout<<nod<<" "<<parinte<<'\n';
    for( auto it : w[ nod ] )
    {
        if( it != parinte )
        {
            if( !nivel[ it ] )
            {
                q.push( make_pair( nod , it ) );
                dfs( it , nod );
                if( intorc[ it ] >= nivel[ nod ] )
                {
                    crt++;
                    do
                    {
                        a = q.top().x;
                        b = q.top().y;
                        q.pop();
                        ans[ crt ].push_back( b );
                    }while( a != nod && b != it );
                    ans[ crt ].push_back( nod );
                }
            }
            ///cout<<it<<endl;
            intorc[ nod ] = min( intorc[ nod ] , intorc[ it ] );
        }
    }
}
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b;
        w[ a ].push_back( b );
        w[ b ].push_back( a );
        ///cout<<a<<" "<<b<<endl;
    }
    dfs( 1 , 0 );
    fout<<crt<<'\n';
    for( i = 1 ; i <= crt ; i++ )
    {
        for( auto it : ans[ i ] )
            fout<<it<<" ";
        fout<<'\n';
    }
}