Cod sursa(job #531897)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 10 februarie 2011 15:44:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
#define M 200001
typedef struct stack
{long st[M],sp;};
stack q;
long n,m,i,j,k,a[M],b[M],deg[N]={0},*g[N],c[N]={0},nr,d[N],f[N],t,timp;

void push(stack &s,long x)
{s.st[++s.sp]=x;}

long pop(stack &s)
{return s.st[s.sp--];}

void parcurgere(long i)
{long j;
c[i]=2;
push(q,i);
for(j=deg[i]-1;j>=0;j--)
if(c[g[i][j]]==1)
       parcurgere(g[i][j]);}

void colectare(long start,long vecin) 
{c[start]=2;
push(q,start);
parcurgere(vecin);
c[start]=1;}

void explorare(long i,long *timp,long *nr)
{long j,k,r;
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]);
             push(q,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("%ld%ld\n",&n,&m);
for(i=1;i<=m;i++)
      {scanf("%ld%ld\n",&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=0;
q.sp=0;
nr=0;
for(i=1;i<=n;i++)
if(c[i]==0)
      if(deg[i]!=0)
             explorare(i,&timp,&nr);
      else
             {c[i]=2;
             push(q,i);
             push(q,0);
             nr++;}
printf("%ld\n",nr);
t=pop(q);
while(q.sp!=0)
      {t=pop(q);
      if(t!=0)
             printf("%ld ",t);
      else
             printf("\n");}
fclose(stdin);
fclose(stdout);
return 0;}