Cod sursa(job #256719)

Utilizator StigmaSimina Pitur Stigma Data 12 februarie 2009 03:20:10
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream.h>

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct nod{int x,y,val;};
nod s[2000];
int a[1000][1000],n,m,nr,v[1000];


void dfs(int nod)
{int i,j;
v[nod]=1;

for (i=1;i<=n;i++)
 if (a[nod][i] && !v[i])
  {nr++;
  a[nod][i]=0;
  a[i][nod]=0;
   s[nr].x=nod;
   s[nr].y=i;
   s[nr].val=m;
   dfs(i);
  }
 else
  if (a[nod][i])
  {a[nod][i]=0;
   a[i][nod]=0;
   for (j=nr;j>1 && s[j].x!=i;j--)
     s[j].val++;
     s[j].val++;
   m+=2;
   dfs(i);
   }
}










int main()
{int i,p1,p2;
fin>>n>>m;
for (i=1;i<=m;i++)
{fin>>p1>>p2;
 a[p1][p2]=a[p2][p1]=1;
 }

m=0;
 dfs(1);
 fout<<m<<'\n';

 m=1;
 fout<<s[1].x<<" ";

 for (i=1;i<=nr;i++)
 {if (m!=s[i].val)
  {m++; fout<<'\n';
  fout<<s[i].x<<" ";
   }
   fout<<s[i].y<<" ";
  }

  fout.close();
  return 0;
}