Cod sursa(job #1385855)

Utilizator Toast97Calin Farcas Toast97 Data 12 martie 2015 15:00:33
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
#include <fstream>

using namespace std;

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

struct nod
{
    int info;
    nod *adr;
} *componente[100005], *v[100005], *s;

void adauga_vecin (int x, int y)
{
    nod *c;
    c = new nod;
    c -> info = y;
    c -> adr = v[x];
    v[x] = c;
}

void adauga_componente (int nrc, int y)
{
    nod *c;
    c = new nod;
    c -> info = y;
    c -> adr = componente[nrc];
    componente[nrc] = c;
}

void adauga_stiva (int info)
{
    nod *c;
    c = new nod;
    c -> info = info;
    c -> adr = s;
    s = c;
}

void sterge_stiva ()
{
    nod *p;
    p = s;
    s = s -> adr;

    delete p;
}

int n, m, lowlink[100005], index[100005], nrcomp = 0;
bool viz[100005];

void citire ()
{
    f >> n >> m;

    int a, b;

    for (int i = 1; i <= m; i ++)
    {
        f >> a >> b;
        adauga_vecin (a, b);
        adauga_vecin (b, a);
    }
}

int minim (int a, int b)
{
    if (a < b)
        return a;
    return b;
}

void dfs (int node, int nivel)
{
    index[node] = nivel;
    lowlink[node] = nivel;
    viz[node] = 1;
    adauga_stiva (node);

    nod *c = v[node];

    int curent;

    while (c)
    {
        curent = c -> info;

        if (viz[curent])
            lowlink[node] = minim (lowlink[node], index[curent]);
        else
        {
            dfs (curent, nivel + 1);
            lowlink[node] = minim (lowlink[node], lowlink[curent]);

            if (index[node] <= lowlink[curent])
            {
                ++ nrcomp;

                int de_adaugat;

                do
                {
                    de_adaugat = s -> info;
                    adauga_componente (nrcomp, de_adaugat);
                    sterge_stiva ();
                }while (de_adaugat != curent);

                adauga_componente (nrcomp, node);
            }
        }

        c = c -> adr;
    }
}

int main()
{
    citire ();

     for (int i = 1; i <= n; i ++)
        if (! viz[i])
            dfs (i, 1);

    g << nrcomp << '\n';

    nod *c;

    for (int i = 1; i <= nrcomp; i ++)
    {
        c = componente[i];

        while (c)
        {
            g << c -> info << " ";
            c = c -> adr;
        }

        g << '\n';
    }

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