Cod sursa(job #900916)

Utilizator andreitulusAndrei andreitulus Data 28 februarie 2013 22:45:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<stdio.h>
#include<vector>
#include<stack>
#define maxn 100003
using namespace std;

int n,m,nrb,t[maxn],v[maxn],nv[maxn],nr;
vector <int> l[maxn],r[maxn];
stack <int> s;


void cit()
{
    int i;

    scanf("%d %d",&n,&m);
    int x,y;

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




void go(int x,int y)
{
    nrb++;

    while(s.top()!=y)
    {
      r[nrb].push_back(s.top());
      s.pop();
    }

    r[nrb].push_back(x);
    r[nrb].push_back(y);
    s.pop();
}





int df(int k,int niv)
{
    int i,nr,nvad,minn;

    s.push(k); v[k]=1;  nv[k]=niv; minn=niv;
    nr=l[k].size();

    for(i=0;i<nr;i++)
      if(v[l[k][i]]==0)
       {
          t[l[k][i]]=k;

          nvad=df(l[k][i],niv+1);

          if(minn>nvad)
              minn=nvad;

          if(niv<=nvad)
           go(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,nr,j;

  printf("%d\n",nrb);

   for(i=1;i<=nrb;i++)
   {
       nr=r[i].size();

       for(j=0;j<nr;j++)
        printf("%d ",r[i][j]);

    printf("\n");
   }
}





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

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

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

}