Cod sursa(job #531730)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 10 februarie 2011 10:22:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
#define M 200001
typedef struct stack
{long st[M],sp;};
stack s,q;
long n,m,deg[N]={0},*g[N],k,i,j,t=0,ind,c[N],l[N],nr,a[M],b[M],u,p,r,v[N]={0};

void push(stack &s,long x)
{s.st[++s.sp]=x;}

long pop(stack &s)
{return s.st[s.sp--];}

void tarjan(long i,long *nr,long *ind)
{long j,r,k;
push(s,i);
if(v[i]==0)
       v[i]=1;
c[i]=(*ind);
l[i]=(*ind)++;
for(j=0;j<deg[i];j++)
if(c[g[i][j]]==0)
       {tarjan(g[i][j],nr,ind);
       if(l[i]>l[g[i][j]])
              l[i]=l[g[i][j]];}
else
       if(v[g[i][j]]==1&&l[i]>c[g[i][j]])
              l[i]=c[g[i][j]];
if(c[i]==l[i])
       {(*nr)++;
       k=0;
       while(s.sp!=0)
             {r=pop(s);
             if(r!=i&&v[r]==1)
                    {push(q,r);
                    k++;
                    v[r]=2;}
             else
                    break;}
       if(v[i]==1)
             {v[i]=2;
             k++;
             push(q,i);}
       if(k==0)
             (*nr)--;
       else
             push(q,0);}}

int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%ld%ld\n",&n,&m);
for(k=1;k<=m;k++)
       {scanf("%ld%ld\n",&a[k],&b[k]);
       deg[a[k]]++;}
for(i=1;i<=n;deg[i++]=0)
       g[i]=(long*)malloc(deg[i]*sizeof(long));
for(j=1;j<=m;j++)
       g[a[j]][deg[a[j]]++]=b[j];
ind=0;
nr=0;
s.sp=0;
q.sp=0;
for(u=1;u<=n;u++)
if(c[u]==0)
       tarjan(u,&nr,&ind);
printf("%ld\n",nr);
r=pop(q);
while(q.sp!=0)
       {r=pop(q);
       if(r==0)
               printf("\n");
       else
               printf("%ld ",r);}
fclose(stdin);
fclose(stdout);
return 0;}