Cod sursa(job #588469)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 8 mai 2011 10:00:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream.h>
#define N 100001
long n,m,i,j,k,a[2*N],b[2*N],deg[N]={0},*g[N],c[N]={0},nr,d[N],f[N],t,timp,q[2*N],p;
void parcurgere(long i)
{long j;
c[i]=2;
q[++p]=i;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
       parcurgere(g[i][j]);}

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

void explorare(long i,long *timp,long *nr)
{long j;
d[i]=f[i]=(*timp)++;
c[i]=1;
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==0)
       {explorare(g[i][j],timp,nr);
       if(f[i]>f[g[i][j]])
               f[i]=f[g[i][j]];
       if(d[i]<=f[g[i][j]])
               {colectare(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];
      deg[a[i]]++,deg[b[i]]++;}
for(j=1;j<=n;deg[j++]=0)
      g[j]=(long*)malloc(deg[j]*sizeof(long));
for(k=1;k<=m;k++)
      {g[a[k]][deg[a[k]]++]=b[k];
      g[b[k]][deg[b[k]]++]=a[k];}
timp=p=nr=0;
for(i=1;i<=n;i++)
if(c[i]==0)
      if(deg[i])
              explorare(i,&timp,&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";}
x.close();
y.close();
return 0;}