Cod sursa(job #1869737)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 februarie 2017 09:32:52
Problema Componente biconexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 3.34 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);
    }

    fclose(f);
}

void dfs(int u, int tata)
{
    dfn[u] = low[u] = ++ timp;

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

    while(p != 0)
    {
       // printf("%d %d %d\n", u, tata, nod[p]);

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

            stk[stkLen].dr = nod[p];
        }

        ///Muchie "arbore"
        if(dfn[nod[p]] == 0)
        {
            dfs(nod[p], u);

            low[u] = mna(low[u], low[nod[p]]);

            ///u Punct de articulatie
            if(low[nod[p]] >= 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 --;

                  //  printf("*%d ", n);

                    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 != nod[p]);

               // printf("\n");
            }
        }

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

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

void solve()
{
    dfs(1, -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;
}