Cod sursa(job #765466)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 7 iulie 2012 19:50:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#define N 100001
int n,m,i,j,k,a[2*N],b[2*N],w[N],*g[N],c[N],nr,d[N],f[N],t,u,q[2*N],p;

void P(int i)
{int j;
c[i]=2;
q[++p]=i;
for(j=w[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
       P(g[i][j]);}

void E(int i)
{int j;
d[i]=f[i]=u++;
c[i]=1;
for(j=w[i]-1;j>=0;j--)
if(!c[g[i][j]])
       {E(g[i][j]);
       if(f[i]>f[g[i][j]])
               f[i]=f[g[i][j]];
       if(d[i]<=f[g[i][j]])
               {c[i]=2,q[++p]=i;
               P(g[i][j]),c[i]=1;
               q[++p]=0,nr++;}}
       else
               if(f[i]>d[g[i][j]])
                       f[i]=d[g[i][j]];}

int main()
{freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
      scanf("%d%d",&a[i],&b[i]),w[a[i]]++,w[b[i]]++;
for(j=1;j<=n;w[j++]=0)
      g[j]=new int[w[j]];
for(k=1;k<=m;k++)
      g[a[k]][w[a[k]]++]=b[k],g[b[k]][w[b[k]]++]=a[k];
for(i=1;i<=n;i++)
if(!c[i])
      if(w[i])
              E(i);
      else
              c[i]=2,q[++p]=i,q[++p]=0,nr++;
printf("%d\n",nr),t=q[p--];
while(p)
     {t=q[p--];
     if(t)
              printf("%d ",t);
     else
              printf("\n");}
return 0;}