Cod sursa(job #2306630)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 decembrie 2018 17:53:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include<cstdio>
#define M(a,b) (a<b?a:b)
const int N=100000,M=200000;
int l,n,i,j,x[M],y[M],e,k,*a[N],u[N],s[N],c[N][N],q,w[N],z[N],t[N];
void T(int i)
{
    for(z[i]=w[i]=++l,s[++q]=i,t[i]=1,j=0;j<u[i];j++)
        if(z[a[i][j]]==-1)
            T(a[i][j]),w[i]=M(w[i],w[a[i][j]]);
        else if(t[a[i][j]])
            w[i]=M(w[i],w[a[i][j]]);
    if(z[i]==w[i])
        for(k++,r=s[q--];r!=i;c[k][++c[k][0]]=r,t[r]=0,r=s[q--]);
}
int main()
{
    freopen("ctc.in","r",stdin),freopen("ctc.out","w",stdout),scanf("%d%d",&n,&e);
    for(i=0;i<e;i++)
    	scanf("%d%d",x+i,y+i),x[i]--,y[i]--,u[x[i]]++;
    for(i=0;i<n;u[i++]=0)
    	z[i]=-1,a[i]=new int[u[i]];
    for(i=0;i<e;i++)
    	a[x[i]][u[x[i]]++]=y[i];
    for(i=0;i<n;i++)
        if(z[i]==-1)
            T(i);
    printf("%d\n",k);
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=c[i][0];j++)
            printf("%d ",c[i][j]+1);
        printf("\n");
    }
}