Cod sursa(job #606394)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 4 august 2011 09:34:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream.h>
#define N 100001
long 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 pa(long i)
{long j;
c[i]=2;
q[++p]=i;
for(j=w[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
       pa(g[i][j]);}

void co(long s,long v)
{c[s]=2,q[++p]=s;
pa(v);
c[s]=1;}

void ex(long i,long *u,long *nr)
{long j;
d[i]=f[i]=(*u)++;
c[i]=1;
for(j=w[i]-1;j>=0;j--)
if(!c[g[i][j]])
       {ex(g[i][j],u,nr);
       if(f[i]>f[g[i][j]])
               f[i]=f[g[i][j]];
       if(d[i]<=f[g[i][j]])
               {co(i,g[i][j]);
               q[++p]=0;
               (*nr)++;}}
       else
               if(f[i]>d[g[i][j]])
                       f[i]=d[g[i][j]];}
int main()
{ifstream x("biconex.in");
ofstream y("biconex.out");
x>>n>>m;
for(i=1;i<=m;i++)
      x>>a[i]>>b[i],w[a[i]]++,w[b[i]]++;
for(j=1;j<=n;w[j++]=0)
      g[j]=(long*)malloc(w[j]*sizeof(long));
for(k=1;k<=m;k++)
      g[a[k]][w[a[k]]++]=b[k],g[b[k]][w[b[k]]++]=a[k];
u=p=nr=0;
for(i=1;i<=n;i++)
if(!c[i])
      if(w[i])
              ex(i,&u,&nr);
      else
              c[i]=2,q[++p]=i,q[++p]=0,nr++;
y<<nr<<"\n";
t=q[p--];
while(p)
     {t=q[p--];
     if(t)
              y<<t<<" ";
     else
              y<<"\n";}
return 0;}