Cod sursa(job #283526)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 19 martie 2009 11:41:26
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
const long NMAX=100010;
const long MMAX=200010;

long *a[NMAX], *b[NMAX], da[MMAX], db[MMAX], x[MMAX], y[MMAX], q[NMAX], p, u, n, m, comp[NMAX], cont;
bool viz[NMAX];

void bfa(long nod);
void bfb(long nod);

int main()
{
	long i, j, k;
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<m; i++)
	{
		scanf("%ld%ld", &x[i], &y[i]);
		da[x[i]]++;
		db[y[i]]++;
	}//for i
	for (i=1; i<=n; i++)
	{
		a[i]=new long(da[i]+1);
		a[i][0]=0;
		b[i]=new long(db[i]+1);
		b[i][0]=0;
	}//for i
	for (i=0; i<m; i++)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		b[y[i]][++b[y[i]][0]]=x[i];
	}//for i
	cont=0;
	k=1;
	while (k<=n)
	{
		cont++;
		bfa(k);
		for (i=0; i<=u; i++)
			comp[q[i]]=-cont;
		bfb(k);
		for (i=0; i<=u; i++)
			if (comp[q[i]]==-cont)
				comp[q[i]]=cont;
		while ((comp[k]>0)&&(k<=n))
			k++;
	}//while
	printf("%ld\n", cont);
	for (i=1; i<=cont; i++)
	{
		for (j=1; j<=n; j++)
			if (comp[j]==i)
				printf("%ld ", j);
		printf("\n");
	}//for i
	return 0;
}//main

void bfa(long nod)
{
	long i;
	for (i=1; i<=n; i++)
		viz[i]=0;
	p=0;
	u=0;
	q[u]=nod;
	viz[nod]=1;
	while (p<=u)
	{
		nod=q[p++];
		for (i=1; i<=a[nod][0]; i++)
			if (!viz[a[nod][i]])
			{
				viz[a[nod][i]]=1;
				q[++u]=a[nod][i];
			}//if
	}//while
}//bfa

void bfb(long nod)
{
	long i;
	for (i=1; i<=n; i++)
		viz[i]=0;
	p=0;
	u=0;
	q[u]=nod;
	viz[nod]=1;
	while (p<=u)
	{
		nod=q[p++];
		for (i=1; i<=b[nod][0]; i++)
			if (!viz[b[nod][i]])
			{
				viz[b[nod][i]]=1;
				q[++u]=b[nod][i];
			}//if
	}//while
}//bfb