Cod sursa(job #275769)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 10 martie 2009 17:34:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <fstream.h>
#define lg_max 250000

struct nod
{
	int inf;
	nod *next;
}*init[lg_max],*trans[lg_max],*rez[lg_max];
int nr,n,m,num;
int viz[lg_max],s[lg_max];

void baga(int a,int b)
{
	nod *q=new nod;
	q->inf=a;
	q->next=init[b];
	init[b]=q;
     q=new nod;
	q->inf=b;
	q->next=trans[a];
	trans[a]=q;
}

void citire()
{
	int a,b;
	scanf ("%d %d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf ("%d %d",&a,&b);
		baga(b,a);
	}
}

void parcurg(int nodd)
{
     viz[nodd]=1;
     for(nod *i=init[nodd];i;i=i->next)
          if(!viz[i->inf])
               parcurg(i->inf);
     s[nr++]=nodd;
}

void creaza(int nodd)
{
     viz[nodd]=1;
     nod *q=new nod;
     q->inf=nodd;
     q->next=rez[num];
     rez[num]=q;
     for (nod *i=trans[nodd];i;i=i->next)
          if (!viz[i->inf])
               creaza(i->inf);
}


void solve()
{
     for (int i=1;i<=n;i++)
          if(!viz[i])
               parcurg(i);
     memset(viz,0,sizeof(viz));
     for (int i=n-1;i>=0;i--)
          if (!viz[s[i]])
          {
               num++;
               creaza(s[i]);
          }
}

void afisare()
{
     printf("%d\n",num);
     for (int i=1;i<=num;i++)
     {
          while (rez[i])
          {
               printf("%d ",rez[i]->inf);
               rez[i]=rez[i]->next;
          }
          printf("\n");
     }
}

int main ()
{
	freopen ("ctc.in","r",stdin);
	freopen ("ctc.out","w",stdout);
	citire();
	solve();
	afisare();
	return 0;
}