Cod sursa(job #582384)

Utilizator rootsroots1 roots Data 15 aprilie 2011 12:07:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <stdio.h>
#include <string.h>

#define MAX 100001

int size,Sol;
char use[MAX],com[MAX];
int 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,i;
	
	p=G[nod];
	
	use[nod]=1;
	low[nod]=niv[nod];
	
	while(p)
	{
		if(p->nod!=T[nod]&&niv[nod]>niv[p->nod]) insert(p->nod,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;
				
				memset(com,0,sizeof(0));
				
				while((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend))
				{
					erase(x,y);
					if((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend)&&(!com[x]))
					{
						add(Sol,x);
						com[0]=1;
						com[x]=1;
					}
					if((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend)&&(!com[y]))
					{
						add(Sol,y);
						com[0]=1;
						com[y]=1;
					}
				}
				
				if(!com[0])
				{
					add(Sol,x);
					add(Sol,y);
				}
			}
		}
		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;
}