Cod sursa(job #1159433)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 29 martie 2014 16:32:28
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <fstream>
#include <vector>

const int NMAX = 100005;
const int MMAX = 200005;

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

int N,M,nv[NMAX],t[NMAX],L[NMAX],x,y,stiva[2][MMAX],lung,rad,nrsol;
bool used[NMAX], afisat[NMAX];
vector <int> v[NMAX];
vector <int> sol[NMAX];

void push(int x, int y)
{
    stiva[0][lung] = x;
    stiva[1][lung] = y;
    lung++;
}

void pop(int *x, int *y)
{
    lung--;
    *x = stiva[0][lung];
    *y = stiva[1][lung];
}

void DFS(int nod)
{
    used[nod] = true;
    L[nod] = nv[nod];

    int x,y;

    for (int i = 0; i < v[nod].size(); ++i)
    {
        if (v[nod][i] != t[nod] && nv[nod] > nv[ v[nod][i] ])
        {
            push(v[nod][i], nod);
        }
        if (!used[ v[nod][i] ])
        {
            nv[ v[nod][i] ] = nv[nod] + 1;
            t[ v[nod][i] ] = nod;

            DFS( v[nod][i] );

            if (L[ v[nod][i] ] < L[nod])
                L[nod] = L[ v[nod][i] ];
            if (nv[nod] <= L[ v[nod][i] ])
            {
                nrsol++;
                do
                {
                    pop(&x, &y);
                    //g << x << " " << y << '\n';
                    sol[nrsol].push_back(x);
                    sol[nrsol].push_back(y);
                }
                while ( (x != nod || y != v[nod][i]) && (x != v[nod][i] || y != nod) );
                //g << '\n';
            }
        }
        else
        if (v[nod][i] != t[nod] && nv[ v[nod][i] ] < L[nod])
            L[nod] = nv[ v[nod][i] ];
    }
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (!used[i])
        {
            rad = i;
            nv[rad] = 1;
            DFS(i);
        }
    }

    g << nrsol << '\n';

    for (int i = 1; i <= nrsol; ++i)
    {
        g << sol[i][0] << " ";
        g << sol[i][1] << " ";
        for (int j = 3; j < sol[i].size() - 1; j+=2)
        {
            g << sol[i][j] << " ";
        }
        g << '\n';
    }

    f.close();
    g.close();
    return 0;
}