Cod sursa(job #1869786)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 februarie 2017 10:13:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.62 kb
#include <cstdio>

#include <cstring>

using namespace std;

FILE *f, *g;

///Lista de muchii
int k;

int nod[2000001];
int urm[2000001];
int lst[1000001];

///Componente biconexe
int bic;

int nbic[2000001];
int ubic[2000001];
int lbic[1000001];

int n, m;

int biComp;
int timp;

int dfn[1000001];
int low[1000001];

///Stiva

int stk[1000001];

int stkLen;

int mna(int a, int b)
{
    return(a < b ? a : b);
}

void add(int a, int b)
{
    k ++;

    nod[k] = b;
    urm[k] = lst[a];

    lst[a] = k;
}

void readFile()
{
    f = fopen("biconex.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    int a, b;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d", &a, &b);

        add(a, b);
        add(b, a);
    }

    fclose(f);
}

void dfs(int u, int parent)
{
    dfn[u] = dfn[parent] + 1;
    low[u] = dfn[u];

    int p = lst[u];
    int st, dr;
    int x, nodVecin;

    stk[++ stkLen] = u;

    while(p != 0)
    {
        x = nod[p];

        if(x != parent)
        {
            ///Muchie "arbore"
            if(dfn[x] == 0)
            {
                dfs(x, u);

                low[u] = mna(low[u], low[x]);

                ///u Punct de articulatie
                if(low[x] >= dfn[u])
                {
                    ///Eticheteaza si scoate componenta biconexa de pe stiva
                    biComp ++;

                    bic ++;

                    nbic[bic] = u;
                    ubic[bic] = lbic[biComp];
                    lbic[biComp] = bic;

                    ///Adauga la componenta curenta
                    do
                    {
                        nodVecin = stk[stkLen --];

                        bic ++;

                        nbic[bic] = nodVecin;
                        ubic[bic] = lbic[biComp];
                        lbic[biComp] = bic;
                    }
                    while(nodVecin != x && stkLen > 0);
                }
            }

            ///Muchie "inapoi"
            else
                low[u] = mna(low[u], dfn[x]);
        }

        ///Urmatorul vecin
        p = urm[p];

    }
}

void solve()
{
    dfs(1, 0);
}

void printFile()
{
    g = fopen("biconex.out", "w");

    fprintf(g, "%d\n", biComp);

    int i, p;
    for(i = 1; i <= biComp; i ++)
    {
        p = lbic[i];

        while(p != 0)
        {
            fprintf(g, "%d ", nbic[p]);

            p = ubic[p];
        }

        fprintf(g, "\n");
    }
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}