Cod sursa(job #1376552)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 5 martie 2015 17:49:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <stack>

#define N 100001
#define M 200001
using namespace std;

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

int n, m;
int t[N], l[N], niv[N];
bool ok[N];

int lst[N], vf[2 * M], vf2[2 * M], urm[2 * M], nvf = 0;

stack<int> s;

int rez[M + 2 * N], nrez = 0;
int cbicnx = 0;

void df(int x)
{
    ok[x] = 1;
    l[x] = niv[x];

    for(int i = lst[x]; i; i = urm[i])
    {
        int y = vf[i];

        if(!ok[y])
        {
            t[y] = x;
            niv[y] = niv[x] + 1;
            s.push(i);
            df(y);

            if(l[y] < l[x])
                l[x] = l[y];

            if(l[y] >= niv[x])
            {
                cbicnx++;
                int j;
                do
                {
                    j = s.top();
                    s.pop();
                    rez[++nrez] = vf[j];
                }while(j != i);
                rez[++nrez] = vf2[i];
                rez[++nrez] = -1;
            }
        }
        else if(y != t[x] && niv[y] < l[x])
            l[x] = niv[y];
    }
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;

        vf[++nvf] = y;
        vf2[nvf] = x;
        urm[nvf] = lst[x];
        lst[x] = nvf;
        vf[++nvf] = x;
        vf2[nvf] = y;
        urm[nvf] = lst[y];
        lst[y] = nvf;
    }

    for(int i = 1; i <= n; i++)
        if(!ok[i])
        {
            niv[i] = 1;
            df(i);
        }

    out << cbicnx << '\n';

    for(int i = 1; i <= nrez; i++)
        if(rez[i] != -1)
            out << rez[i] << ' ';
        else
            out << '\n';
    return 0;
}