Cod sursa(job #280039)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 13 martie 2009 10:19:36
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
//Componente tare conxe BC
#include <stdio.h>
#include <fstream.h>
#define lg_max 1000

struct no
{
	int inf;
	no *next;
}*G[lg_max],*GT[lg_max],*rez[lg_max],*aux;

int sir[lg_max],num,n,m;
char viz[lg_max];

void baga(no *&X,int dest)
{
	no *q=new no;
	q->inf=dest;
	q->next=X;
	X=q;
}

void citire()
{
	int x,y;

	freopen ("ctc.in","r",stdin);
	freopen ("ctc.out","w",stdout);

	scanf ("%d %d",&n,&m);
	for (int i=0;i<m;i++)
	{
		scanf ("%d %d",&x,&y);
		baga(G[x],y);
		baga(GT[y],x);
	}
}

void df(int nod)
{
	viz[nod]='1';
	for (no *q=G[nod];q;q=q->next)
		if (!viz[q->inf])
			df(q->inf);
	sir[num++]=nod;
}

void df2(int nod)
{
  viz[nod]='1';
  aux=new no;
  aux->inf=nod;
  aux->next=rez[num];
  rez[num]=aux;
  for (no *q=GT[nod];q;q=q->next)
	if (!viz[q->inf])
	    df2(q->inf);
}

void solve()
{
	for (int i=1;i<=n;i++)
		if (!viz[i])
			df(i);
	memset(viz,0,sizeof(viz));
	num=0;
	for (int j=n-1;j>=0;j--)
		if(!viz[sir[j]])
		{
			df2(sir[j]);
			num++;
		}

	//afisare();
	printf("%d\n",num);
	for (int p=0;p<num;p++)
	{
		for (no *q=rez[p];q;q=q->next)
			printf("%d ",q->inf);
		printf("\n");
	}
}

int main ()
{
	citire();
	solve();
	return 0;
}