Cod sursa(job #1869751)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 februarie 2017 09:48:29
Problema Componente biconexe Scor 56
Compilator cpp Status done
Runda Arhiva educationala Marime 3.33 kb
#include <cstdio>

#include <cstring>

using namespace std;

FILE *f, *g;

///Lista de arce
int k;

int nod[200001];
int urm[200001];
int lst[100001];

///Componente biconexe
int bic;

int nbic[200001];
int ubic[200001];
int lbic[100001];

int n, m;

int biComp;
int timp;

int dfn[100001];
int low[100001];

///Stiva
bool onStack[100001];

struct muchie
{
    int st, dr;
};

muchie stk[100001];

int stkLen;

inline 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 tata)
{
    dfn[u] = low[u] = ++ timp;

    int p = lst[u];
    int st, dr;
    int x;
    while(p != 0)
    {
        x = nod[p];

        ///Nod adiacent, diferit de tata, deasupra lui u in arborel DFS, pun muchia in stiva
        if(x != tata && dfn[x] < dfn[u])
        {
            stk[++ stkLen].st = u;

            stk[stkLen].dr = x;
        }

        ///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 ++;

                memset(onStack, 0, sizeof(onStack));

                do
                {
                    st = stk[stkLen].st;
                    dr = stk[stkLen].dr;

                    stkLen --;

                    if(onStack[st] == 0)
                    {
                        onStack[st] = 1;

                        ///Adauga la componenta biconexa curenta
                        bic ++;

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

                        lbic[biComp] = bic;
                    }

                    if(onStack[dr] == 0)
                    {
                        onStack[dr] = 1;

                        ///Adauga la componenta biconexa curenta
                        bic ++;

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

                        lbic[biComp] = bic;
                    }
                }
                while(st != u && dr != x && stkLen > 0);
            }
        }

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

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

void solve()
{
    int i;
    for(i = 1; i <= n; i ++)
    {
        if(dfn[i] == 0)
           stkLen = 0, dfs(i, -1);
    }
}

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;
}