Cod sursa(job #892713)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 26 februarie 2013 11:22:10
Problema Componente biconexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fi ("biconex.in");
ofstream fo ("biconex.out");

const int dim = 100004;
int N, M, NB, NR, low[dim], niv[dim];
vector <int> V[dim], R[dim];
stack < pair <int, int> > S;

void cit ()
{
    fi >> N >> M;
    for (int i = 1, x, y; i <= M; i++)
    {
        fi >> x >> y;
        V[x].push_back (y);
        V[y].push_back (x);
    }
}

void dfs (int n, int t)
{
    niv[n] = low[n] = niv[t] + 1;
    S.push (make_pair (n, t));
    for (int i = 0, f; i < V[n].size(); i++)
    {
        f = V[n][i];
        if (niv[f] == 0)
        {
            dfs (f, n);

            low[n] = min (low[f], low[n]);
            if (low[f] >= niv[n])
            {
                int nn = n - 1, tt = t - 1;
                NB ++;

                while ( !(nn == n && tt == t) )
                {
                    nn = S.top().first;
                    tt = S.top().second;
                    S.pop();
                    R[NB].push_back (nn);
                }
                S.push (make_pair (nn, tt));
            }
        }
        else if (f != t)
        {
            low[n] = min (low[f], niv[n]);
        }
    }
}

void afi ()
{
    int i, j;
    fo << NB << '\n';
    for (i = 1; i <= NB; i++)
    {
        for (j = 0; j < R[i].size(); j++)
        {
            fo << R[i][j] << ' ';
        }
        fo << '\n';
    }

}

int main ()
{
    cit ();
    for (int i = 1; i <= N; i++)
    {
        if (low[i] == 0)
        {
            dfs (i, 0);
        }
    }
    afi ();
    return 0;
}