Cod sursa(job #982883)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 10 august 2013 13:56:13
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define Nmax 50000

class edge
{
    public:

        int x;
        int y;
};

vector <int> SOL[Nmax];
vector <int> G[Nmax];
vector <int> low(Nmax);
vector <int> dfn(Nmax);

stack <edge> ST;

int N, M, NR;

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();
}

void biconex( int nod, int fiu )
{
    int x, y;
    edge a;
    NR++;

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

        SOL[NR].push_back( a.x );
        SOL[NR].push_back( a.y );

    } while( a.x != nod || a.y != fiu );
}

void DF( int nod, int tata, int number )
{
    low[nod] = dfn[nod] = number;

    for ( unsigned i = 0; i < G[nod].size(); ++i )
    {
        if ( G[nod][i] == tata )
                continue;

        if ( dfn[ G[nod][i] ] == -1 )
        {
            edge a = { nod, G[nod][i] };
            ST.push( a );
            DF( G[nod][i], nod, number + 1 );
            low[nod] = min( low[nod], low[ G[nod][i] ] );

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

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

    g << NR << "\n";

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

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

        g << "\n";
    }

    g.close();
}


int main()
{
    read();
    DF( 1, 0, 0 );
    print();

    return 0;
}