Cod sursa(job #630555)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 5 noiembrie 2011 19:24:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
# include <fstream>
#define minim(x,y) (x<y? x:y) 
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int n,m,x,y,nr,nrdf[100005],v[100005],k,tata[100005],i;
 
 struct nod 
 {
	 int info;
	 nod *urm;
 }*a[100005],*p,*cb[100005];

 class stiva 
 {
	 public:
	 int vf;
	 int sti[200005],stj[200005];
	   
	 stiva (){vf=0;}
	void push (int x,int y)
	{
		vf++;
		sti[vf]=x;
		stj[vf]=y;
	}
 
	void pop (int &i,int &j)
	{
		i=sti[vf];
		j=stj[vf];
		vf--;
		
	}
 
 
 }st;
 
 
 
  void biconex (int i)
  {
	  nr++;
	  nrdf[i]=nr;
	  v[i]=nr;
	  
	  nod *p;
	  p=a[i];
	  while (p)
	  {
		  if (nrdf[p->info]==0)
		  {
			  st.push (i,p->info);
			  tata[p->info]=i;
			  biconex (p->info);
			  v[i]=minim (v[i],v[p->info]);
			  if (v[p->info]>=nrdf[i])
			  {
				  int x,y;
				  k++;
				  while (!(st.sti[st.vf]==i && st.stj[st.vf]==p->info) && st.vf>0)
				  {
					  nod *p;
					  st.pop (x,y);
					  p=new nod;
					  p->info=y;
					  p->urm=cb[k];
					  cb[k]=p;
				  }
				  if (st.vf!=0)
				  {
					  nod *p;
					  st.pop (x,y);
				  p=new nod;
				  p->info=x;
				  p->urm=cb[k];
				  cb[k]=p;
				  
				  p=new nod;
				  p->info=y;
				  p->urm=cb[k];
				  cb[k]=p;
				  }
			  }
			  
		  }
		  else
			  if (tata[i]!=p->info)
				  v[i]=minim (v[i],nrdf[p->info]);
		p=p->urm;
	  }
  }
 

int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		p=new nod;
		p->info=y;
		p->urm=a[x];
		a[x]=p;
		p=new nod;
		p->info=x;
		p->urm=a[y];
		a[y]=p;
	}
	
	for (i=1;i<=n;i++)
		if (nrdf[i]==0)
			biconex (i);
		
		g<<k<<"\n";
	for (i=1;i<=k;i++)
	{
		p=cb[i];
		while (p)
		{
			g<<p->info<<" ";
			p=p->urm;
		}
		g<<"\n";
	}
	
	
	
	return 0;
	
}