Cod sursa(job #1268397)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 20 noiembrie 2014 21:53:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 2;

vector <int> G[Nmax];
vector <int> CB[Nmax];
stack < pair<int,int> > ST;

int low[Nmax], dfn[Nmax];
int vis[Nmax];

int N, M, B;

void biconex( int nod, int x )
{
    B++;
    pair<int,int> p;

    do
    {
        p = ST.top();
        ST.pop();

        CB[B].push_back( p.first );
        CB[B].push_back( p.second );

    } while ( p.first != nod || p.second != x );

}

void DFS( int nod, int nr )
{
    low[nod] = dfn[nod] = nr;
    vis[nod] = 1;

    for ( auto x: G[nod] )
    {
        if ( !vis[x] )
        {
            ST.push( pair<int,int>( nod, x ) );
            DFS( x, nr + 1 );
            low[nod] = min( low[nod], low[x] );

            if ( low[x] >= dfn[nod] )
            {
                biconex( nod, x );
            }
        }
        else
        {
            low[nod] = min( low[nod], dfn[x] );
        }
    }
}

void print()
{
    ofstream g("biconex.out");

    g << B << "\n";

    for ( int i = 1; i <= B; ++i )
    {
        sort( CB[i].begin(), CB[i].end() );
        CB[i].erase( unique( CB[i].begin(), CB[i].end() ), CB[i].end() );

        for ( unsigned j = 0; j < CB[i].size(); ++j )
                g << CB[i][j] << " ";

        g << "\n";
    }

    g.close();
}

void read()
{
    ifstream f("biconex.in");

    f >> N >> M;

    for ( int i = 1, a, b; i <= M; ++i )
    {
        f >> a >> b;

        G[a].push_back( b );
        G[b].push_back( a );
    }

    for ( int i = 1; i <= N; ++i )
            dfn[i] = -1;

    f.close();
}

int main()
{
    read();
    DFS( 1, 1 );
    print();

    return 0;
}