Cod sursa(job #2306661)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 decembrie 2018 18:20:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include<cstdio>
const int N=100001;
int n,m,a[N],c,r,*u[N],*v[N],s[10000][2000],w[N],z[N],x[2*N],y[2*N],i,j;
bool b[N];
void A(int i)
{
    if(b[i])
		return;
	for(b[i]=1,j=0;j<w[i];j++)
		A(u[i][j]);
    a[++c]=i;
}
void B(int i)
{
    if(!b[i])
		return;
	for(b[i]=j=0;j<z[i];j++)
    	B(v[i][j]);
    s[r][++s[r][0]]=i;
}
int main()
{
    freopen("ctc.in","r",stdin),freopen("ctc.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    	scanf("%d%d",x+i,y+i),w[x[i]]++,z[y[i]]++;
    for(i=1;i<=n;i++)
    	u[i]=new int[w[i]],v[i]=new int[z[i]],w[i]=z[i]=0;
    for(i=0;i<m;i++)
    	u[x[i]][w[x[i]]++]=y[i],v[y[i]][z[y[i]]++]=x[i];
    for(i=1;i<=n;i++) 
		A(i);
    for(i=n;i;i--) 
		if(b[a[i]]) 
			r++,B(a[i]);
	for(printf("%d\n",r),i=r;i;i--)
	{
		for(j=1;j<=s[i][0];j++)
			printf("%d ",s[i][j]);
		printf("\n");
	}
}