Cod sursa(job #700225)

Utilizator gabriel93Robu Gabriel gabriel93 Data 1 martie 2012 08:17:45
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<cstring>
using namespace std;
int n,m,k;
int viza[100002],vizb[100002];

struct nod
{
	int v;
	nod *adresa;
};
nod *a[100002],*b[100002];

void add(int x,int y)
{
	nod *p;
	p=new nod;
	p->v=y;
	p->adresa=a[x];
	a[x]=p;
	
	p=new nod;
	p->v=x;
	p->adresa=b[y];
	b[y]=p;
}

void citire()
{
	int i,x,y;
	scanf("%d %d",&n,&m);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		add(x,y);
	}
	fclose(stdin);
}

void dfa(int x)
{
	nod *p;
	viza[x]=k;
	for(p=a[x];p;p=p->adresa)
		if(viza[p->v]==0)
			dfa(p->v);
}

void dfb(int x)
{
	nod *p;
	vizb[x]=k;
	for(p=b[x];p;p=p->adresa)
		if(vizb[p->v]==0)
			dfb(p->v);
}

void scrie()
{
	int i,j;
	printf("%d\n",k);
	for(i=1;i<=k;i++)
	{
		for(j=1;j<=n;j++)
			if(viza[j]==i)
				printf("%d ",j);
		printf("\n");
	}
	fclose(stdout);
}

int vmin(int x,int y)
{
	return(x<y)?x:y;
}

int main()
{
	int i,j,q;
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	k=0;
	for(i=1;i<=n;i++)
		if(viza[i]==0 && vizb[i]==0)
		{
			++k;
			dfa(i);
			dfb(i);
			for(j=1;j<=n;j++)
			{
				q=vmin(viza[j],vizb[j]);
				viza[j]=q;
				vizb[j]=q;
			}
		}
	scrie();
	return 0;
}