Cod sursa(job #2306663)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 decembrie 2018 18:25:15
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<vector>
const int N=100001;
vector<int> s[N];
int n,m,a[N],c,r,*u[N],*v[N],w[N],z[N],x[2*N],y[2*N],i,j;
bool b[N];
void A(int i)
{
    if(b[i])
		return;
	int j;
	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;
	int j;
	for(b[i]=j=0;j<z[i];j++)
    	B(v[i][j]);
    s[r].push_back(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(c=s[i].size(),j=0;j<c;j++)
			printf("%d ",s[i][j]);
		printf("\n");
	}
}