Cod sursa(job #2133375)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 16 februarie 2018 20:56:54
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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 < int > q;
vector < int > w[nmax],ans[nmax];
void dfs( int nod , int parinte )
{
    nivel[ nod ] = intorc[ nod ] = nivel[ parinte ] + 1;
    for( auto it : w[ nod ] )
    {
        if( it != parinte )
        {
            if( !nivel[ it ] )
            {
                q.push( it );
                dfs( it , nod );
                if( intorc[ it ] >= nivel[ nod ] )
                {
                    crt++;
                    a = 0;
                    do
                    {
                        a = q.top();
                        q.pop();
                        ans[ crt ].push_back( a );
                    }while( a != it );
                    ans[ crt ].push_back( nod );
                }
            }
            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 );
    }
    dfs( 1 , 0 );
    fout<<crt<<'\n';
    for( i = 1 ; i <= crt ; i++ )
    {
        for( auto it : ans[ i ] )
            fout<<it<<" ";
        fout<<'\n';
    }
}