Cod sursa(job #300807)

Utilizator StigmaSimina Pitur Stigma Data 7 aprilie 2009 18:20:21
Problema Componente biconexe Scor 48
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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,n0;
int sol[dim],v[dim];
stiva *end;


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,r1,r2,N;
nr++;
pop (&x, &y);
N=n0;
n0++; sol[n0]=x; v[n0]=nr;
r1=x;r2=y;
n0++; sol[n0]=y; v[n0]=nr;
		
while ((x!=F  &&  y!=S))
 {n0++; 
  pop (&x, &y);
  if (sol[n0-1]==x) 
  sol[n0]=y; 
  else sol[n0]=x;
  v[n0]=nr;
  }
 
 if (n0-N>2 && (sol[n0]==r1 || sol[n0]==r2)) n0--;

}		 

void dfs(int k)
{list *p;
int x,y;

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;
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]<<" ";
	for(i++;v[i]==v[i-1] && i<=n0;i++)
		fout<<sol[i]<<" ";
fout<<'\n';
}

fout.close();
return 0;
}