Cod sursa(job #893908)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 26 februarie 2013 18:42:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

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

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

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

void dfs (int n, int t)
{
    low[n] = niv[n] = niv[t] + 1;

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

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

                while ( !(nn == n && ff == f) )
                {
                    ff = S.top().first;
                    nn = S.top().second;

                    S.pop ();

                    R[NB].push_back (nn);
                    R[NB].push_back (ff);
                }
            }
        }
        else
        {
            low[n] = min (low[n], low[f]);
        }
    }
}

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

        fo << R[i][0] << ' ';
        for (j = 1; j < R[i].size(); j++)
            if (R[i][j] != R[i][j-1])
                fo << R[i][j] << ' ';
        fo << '\n';
    }
}

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

    return 0;
}