Cod sursa(job #1378892)

Utilizator heracleRadu Muntean heracle Data 6 martie 2015 14:58:55
Problema Componente biconexe Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <vector>

FILE* in=fopen("biconex.in","r");
FILE* out=fopen("biconex.out","w");

const int Q=100007,W=200007;

int lst[Q],val[2*W],nxt[2*W],nr;

void add(int a, int b)
{
    val[++nr]=b;
    nxt[nr]=lst[a];
    lst[a]=nr;
}

int n,m;

int viz[Q];



std:: vector<int> lista;

int nrc;

std::vector<int> comp[Q];

int h[Q];

int dfs(int nod, int tata)
{
    int up=0;

    int p=lst[nod];

    h[nod]=h[tata]+1;

    lista.push_back(nod);

    viz[nod]=1;

    int act;

    while(p)
    {
        if(viz[val[p]]==2)
        {
            p=nxt[p];
            continue;
        }
        if(viz[val[p]]==0)
        {
            act=dfs(val[p],nod);
            if(h[act]<h[up])
                up=act;

            if(act==nod)
            {
                nrc++;

                while(lista.back()!=nod)
                {
                    comp[nrc].push_back(lista.back());
                    lista.pop_back();
                }
                comp[nrc].push_back(lista.back());

                up=0;
            }
        }
        else
        {
            if(h[val[p]]<h[up])
                up=val[p];
        }
       // }



        p=nxt[p];
    }

    viz[nod]=2;
    return up;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b;

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

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

    h[0]=Q;
    dfs(1,Q-1);

    fprintf(out,"%d\n",nrc);

    for(int i=1; i<=nrc; i++)
    {
        for(int j=0; j<comp[i].size(); j++)
            fprintf(out,"%d ",comp[i][j]);
        fprintf(out,"\n");
    }

    return 0;
}