Cod sursa(job #1361049)

Utilizator danalex97Dan H Alexandru danalex97 Data 25 februarie 2015 19:21:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream F("biconex.in");
ofstream G("biconex.out");

const int N = 100010;

int n,m,lvl[N],bestlvl[N],mk[N],ans;
vector<int> v[N],s1,s2,sol[N];

void dfs(int x,int dd)
{
    lvl[x] = lvl[dd] + 1;
    bestlvl[x] = lvl[x];
    for (int i=0;i<int(v[x].size());++i)
    {
        int y = v[x][i];
        if ( lvl[y] == 0 )
        {
            s1.push_back(x);
            s2.push_back(y);
            dfs(y,x);

            bestlvl[x] = min(bestlvl[x],bestlvl[y]);
            if ( bestlvl[y] >= lvl[x] )
            {
                ++ans;
                if ( !s1.empty() )
                    while ( 1 )
                    {
                        int ok = ( s1.back()!=x || s2.back()!=y );
                        if ( mk[s1.back()] != ans ) mk[s1.back()] = ans, sol[ans].push_back( s1.back() );
                        if ( mk[s2.back()] != ans ) mk[s2.back()] = ans, sol[ans].push_back( s2.back() );
                        s1.pop_back(), s2.pop_back();
                        if ( !ok ) break;
                        if ( s1.empty() ) break;
                    }
            }
        }
        else
            if ( y != dd )
                bestlvl[x] = min(bestlvl[x],lvl[y]);
    }
}

int main()
{
    F>>n>>m;
    for (int i=1,x,y;i<=m;++i)
    {
        F>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    G<<ans<<'\n';
    for (int i=1;i<=ans;++i)
    {
        for (int j=0;j<int(sol[i].size());++j)
            G<<sol[i][j]<<' ';
        G<<'\n';
    }
}