Cod sursa(job #300863)

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

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

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



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


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

}

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


void comp_noua(int S, int F)
{int 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(int 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()
{int i,x,y,m;

	fin>>n>>m;
for (i=1;i<=m;i++)
   {fin>>x>>y; add(x,y); add(y,x);}
   
nr=0;   
   

	
nv[1]=1;
dfs(1);

fout<<nr<<'\n';	



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

fout.close();
return 0;
}