Cod sursa(job #300828)

Utilizator StigmaSimina Pitur Stigma Data 7 aprilie 2009 18:31:26
Problema Componente biconexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream.h>
#define dim 100005
ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct list{long nod; list *urm;};
struct stiva{long x,y; stiva *urm,*pred;};

list *L[dim];
long nv[dim], l[dim], t[dim];
long n,nr,n0;
long sol[dim],v[dim],u[dim];
stiva *end;



void add(long x, long y)
{list *p=new list;
p->nod=y;
p->urm=L[x];
L[x]=p;
}


void push(long x, long y)
{stiva *q=new stiva;
q->x=x;
q->y=y;
q->urm=0;
q->pred=end;
end=q;

}

void pop(long *x, long *y)
{stiva *d;
d=end;
 *x=end->x;
 *y=end->y;
 end=end->pred;
 delete d;
}
 


void comp_noua(long S, long F)
{long x,y;

nr++;
pop (&x, &y);
n0++; sol[n0]=x; v[n0]=nr;
n0++; sol[n0]=y; v[n0]=nr;
u[x]=nr; u[y]=nr;
		
while ((x!=F  ||  y!=S) && (y!=F  ||  x!=S))
 {pop (&x, &y);
  
  if (u[x]!=nr) 
  { n0++; u[x]=nr;
   sol[n0]=x;
	v[n0]=nr;
  }
  
  if (u[y]!=nr) 
  { n0++; u[y]=nr;
   sol[n0]=y;
	v[n0]=nr;
  }
 
 
  }
 
 

}		 

void dfs(long k)
{list *p;


l[k]=nv[k];

for (p=L[k];p;p=p->urm)
 {if (p->nod!=t[k] && nv[k]>nv[p->nod])
	 push(p->nod,k); 
	if(!t[p->nod])
		{nv[p->nod]=nv[k]+1;
	     t[p->nod]=k;
	  
	     dfs(p->nod);
	  
	     if (l[k]>l[p->nod]) l[k]=l[p->nod];
	     if (l[p->nod]>=nv[k]) 
		   comp_noua(k,p->nod);
	      
		 }
	 else //am mai trecut prin el
		 if (p->nod!=t[k] && nv[p->nod]<l[k])
			 l[k]=nv[p->nod];
 }	 
		 
}		 


int main()
{long i,x,y,m;
list *q;
	fin>>n>>m;
for (i=1;i<=m;i++)
   {fin>>x>>y; add(x,y); add(y,x);}
   
 for (i=1;i<=n;i++)
   if (!t[i])
    {nv[i]=1;
     t[i]=-1;
     dfs(i);
	 }
	
fout<<nr<<'\n';	

i=1;
while(i<=n0) 
{fout<<sol[i]<<" ";
 nr=v[i];
  i++;
	for(;v[i]==nr && i<=n0;i++)
		fout<<sol[i]<<" ";
fout<<'\n';
}

fout.close();
return 0;
}