Cod sursa(job #1378528)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 6 martie 2015 12:46:11
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAXN = 100000, MAXM = 200000;

int N, M, level[MAXN+1], low[MAXN+1], viz[MAXN+1], T[MAXN+1], fiiRad = 0, rad, afis[MAXN+1], cnt;

vector <int> G[MAXN+1], sol[MAXN+1];

struct muchie
{
    int x;
    int y;
};

void citire()
{
    in>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        int x, y; in>>x>>y;
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }
}

stack <muchie> st;

void dfs(int nod)
{
    viz[ nod ] = 1; low[ nod ] = level[ nod ];

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

        if( viz[ next ] == 0 )
        {
            level[ next ] = level[ nod ] + 1; T[ next ] = nod;
            muchie m; m.x = nod; m.y = next; st.push( m );
            dfs( next );

            if( nod == rad )
                fiiRad++;

            low[ nod ] = min( low[ nod ], low[ next ] );



            if( ( level[ nod ] <= low[ next ] ) || ( next == rad && fiiRad >= 2 ) )
            {
                 //cout<<nod<<' '<<next<<endl;

                memset(afis,0,sizeof(afis));

                while( !( (st.top()).x == nod && (st.top()).y == next ) )
                {
                    int x = (st.top()).x, y = (st.top()).y;
                    //cout<<x<<' '<<y<<' ';

                    if( afis[ x ] == 0 )
                        //out<<x<<' ';
                        sol[cnt].push_back(x);
                    if( afis[ y ] == 0 )
                        //out<<y<<' ';
                        sol[cnt].push_back(y);
                    afis[ x ] = 1, afis[ y ] = 1;
                    st.pop();
                }

                if( afis[ nod ] == 0 )
                    //out<<nod<<' ';
                    sol[ cnt ].push_back(nod);
                if( afis[ next ] == 0 )
                    //out<<next;
                    sol[ cnt ].push_back(next);
                //cout<<nod<<' '<<next<<endl;

                //out<<endl;

                st.pop();

                cnt++;
            }
        }
        else if( next != T[ next ] )
        {
            low[ nod ] = min( low[ nod ], level[ next ] );
        }
    }
}




int main()
{
    citire();
    rad = 1;
    dfs(rad);
    out<<cnt<<endl;
    for(int i = 0; i < cnt; i++)
    {
        for(int j = 0; j < sol[ i ].size(); j++)
            out<<sol[ i ][ j ]<<' ';
        out<<endl;
    }
    return 0;
}