Cod sursa(job #916716)

Utilizator andrettiAndretti Naiden andretti Data 16 martie 2013 20:12:33
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;

const int maxn=100005;
int n,m,nrc;
int v[maxn],nv[maxn],t[maxn];
vector <int> l[maxn],sol[maxn];
stack <int> s;

void cit()
{
    int i;
    int x,y;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        l[x].push_back(y);
        l[y].push_back(x);
    }
}

void add(int x,int y)
{
    nrc++;
    while(s.top()!=y)
    {
        sol[nrc].push_back(s.top());
        s.pop();
    }

    sol[nrc].push_back(y);
    sol[nrc].push_back(x);
    s.pop();
}

int df(int k,int niv)
{
    int aux,minn,ok=0;

    s.push(k);
    v[k]=1; nv[k]=niv; minn=niv;
    for(unsigned int i=0;i<l[k].size();i++)
        if(v[l[k][i]]==0)
        {
            t[l[k][i]]=k;
            aux=df(l[k][i],niv+1);
            if(minn>aux && ok==0) minn=aux.ok=1;
            if(aux>=niv) add(k,l[k][i]);
        }
        else
          if(minn>nv[l[k][i]] && l[k][i]!=t[k]) minn=nv[l[k][i]];

    return minn;
}

void afis()
{
    int i;

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

int main()
{
    int aux;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    cit();
    aux=df(1,1);
    afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}