Cod sursa(job #582376)

Utilizator rootsroots1 roots Data 15 aprilie 2011 11:56:25
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <stdio.h>

#define MAX 100001

int size,Sol;
int use[MAX],niv[MAX],T[MAX],low[MAX];

struct coord
{
	int x,y;
}stack[MAX];

struct graf
{
	int nod;
	graf *link;
}*G[MAX];

struct vector
{
	int nod;
	vector *link;
}*v[MAX];

inline void add(int x,int y)
{
	vector *p;
	
	p=new vector;
	p->nod=y;
	p->link=v[x];
	v[x]=p;
}

inline void addnod(int x,int y)
{
	graf *p;
	
	p=new graf;
	p->nod=y;
	p->link=G[x];
	G[x]=p;
}

inline void insert(int x,int y)
{
	stack[++size].x=x;
	stack[size].y=y;
}

inline void erase(int &x,int &y)
{
	x=stack[size].x;
	y=stack[size].y;
	size--;
}

inline void df(int nod)
{
	graf *p;
	int x,y,Xend,Yend;
	
	p=G[nod];
	
	use[nod]=1;
	low[nod]=niv[nod];
	
	while(p)
	{
		if(p->nod!=T[nod]&&niv[nod]>niv[p->nod]) insert(nod,p->nod);
		
		if(!use[p->nod])
		{
			T[p->nod]=nod;
			niv[p->nod]=niv[nod]+1;
			
			df(p->nod);
			
			if(low[p->nod]<low[nod]) low[nod]=low[p->nod];
			else
			if(low[p->nod]>=niv[nod])
			{
				Xend=nod;
				Yend=p->nod;
				
				Sol++;
				
				x=0;
				y=0;
				erase(x,y);
				
				add(Sol,x);
				add(Sol,y);
				
				while((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend))
				{
					erase(x,y);
					if((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend)) add(Sol,x);
				}
			}
		}
		else
		if(p->nod!=T[nod]&&low[nod]>niv[p->nod]) low[nod]=niv[p->nod];
		
		p=p->link;
	}
}

inline void screen(int nod)
{
	vector *p;
	
	p=v[nod];
	
	while(p)
	{
		printf("%d ",p->nod);
		p=p->link;
	}
}

int main()
{
	int N,M,i,x,y;
	
	freopen("biconex.in","r",stdin);
	
	scanf("%d%d",&N,&M);
	
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&x,&y);
		addnod(x,y);
		addnod(y,x);
	}
	
	for(i=1;i<=N;i++)
	{
		T[i]=0;
		use[i]=0;
		niv[i]=0;
		low[i]=0;
	}
	
	for(i=1;i<=N;i++)
		if(!use[i])
		{
			niv[i]=1;
			size=1;
			df(i);
		}
	
	freopen("biconex.out","w",stdout);
	
	printf("%d\n",Sol);
	
	for(i=1;i<=Sol;i++)
	{
		screen(i);
		printf("\n");
	}
	
	return 0;
}