Cod sursa(job #303046)

Utilizator rethosPaicu Alexandru rethos Data 9 aprilie 2009 14:58:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#define NM 100001
int st[NM];
int vf;
int n,m;
int ind[NM],low[NM],viz[NM];
int index;
int nr;
struct list{int nod;list *urm;} *rez[NM],*g[NM];
void df(int k);
inline void add(int x,int a)
{list *p=new list;
 p->nod=a;
 p->urm=g[x];
 g[x]=p;
}
inline void addsol(int x,int a)
{list *p=new list;
 p->nod=a;
 p->urm=rez[x];
 rez[x]=p;
}
int main()
{freopen("ctc.in","r",stdin);
 freopen("ctc.out","w",stdout);
 int i,x,y;
 scanf("%d %d",&n,&m);
 for (i=1;i<=m;i++)
	 {scanf("%d %d",&x,&y);
	  add(x,y);
	 }
 for (i=1;i<=n;i++)
	 if (!ind[i])
		 {df(i);
		 }
 printf("%d\n",nr);
 list *p;
 for (i=1;i<=nr;i++)
	 {for (p=rez[i];p;p=p->urm)
		 {printf("%d ",p->nod);
		 }
	  printf("\n");
	 }
 return 0;
}
void df(int k)
{index++;
 ind[k]=index;
 low[k]=index;
 st[++vf]=k;
 list *p;
 for (p=g[k];p;p=p->urm)
    if (!viz[p->nod])
	 {if (!ind[p->nod])
		 {df(p->nod);
		 }
	  if (low[p->nod]<low[k]) low[k]=low[p->nod];
	 }
 if (low[k]==ind[k])
	 {nr++;
	  while (st[vf]!=k)
		  {viz[st[vf]]=1;
		   addsol(nr,st[vf]);
		   vf--;
		  }
      addsol(nr,k);
	  viz[k]=1;
	  vf--;	  	  
	 }
}