Cod sursa(job #1032915)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 16 noiembrie 2013 10:58:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<fstream>
#include<vector>
#include<set>
#include<stack>
#include<utility>

using namespace std;

#define max_n 100010
#define max_m 200010

ifstream f("biconex.in");
ofstream g("biconex.out");

int n , m , k;

vector< int > L[max_n];
stack< pair<int  , int> >S;
set<int> Sol[max_m];
set<int>::iterator it;

bool Viz[max_n];
int Low[max_n];

void read(){

    int nod_a , nod_b;

    f>>n>>m;

    for( int i = 1 ; i <= m ; i++ ){
        f>>nod_a>>nod_b;
        L[nod_a].push_back(nod_b);
        L[nod_b].push_back(nod_a);
    }

}

void dfs( int nod , int niv , int father ){

    int next_nod;

    Viz[nod] = true; Low[nod] = niv;

    for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){

        next_nod = L[nod][i];

        if( next_nod == father )
            continue;

        if( !Viz[next_nod] ){

            S.push( make_pair(nod , next_nod) );

            dfs( next_nod , niv + 1 , nod );

            if( niv <= Low[next_nod] && S.size() ){
                pair<int , int> p(nod , next_nod); k++;
                while( p != S.top() ){
                    Sol[k].insert( S.top().first );
                    Sol[k].insert( S.top().second );
                    S.pop();
                }
                Sol[k].insert( S.top().first );
                Sol[k].insert( S.top().second );
                S.pop();
            }

        }

        if( Low[next_nod] < Low[nod] )
            Low[nod] = Low[next_nod];
    }

}

void solve(){

    for( int i = 1 ; i <= n ; i++ )
        if( !Viz[i] )
            dfs(i , 1 , 0);

}

void print(){

    g<<k<<"\n";

    for( int i = 1 ; i <= k ; i++ ){
        for( it = Sol[i].begin() ; it != Sol[i].end() ; it++ )
            g<<(*it)<<" ";
        g<<"\n";
    }

}

int main(){

    read();

    solve();

    print();

    return 0;
}