Cod sursa(job #765462)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 7 iulie 2012 19:43:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#define N 100001
int n,m,w[N],*g[N],i,d,c[N],l[N],nr,a[2*N],b[2*N],v[N],s[2*N],q[2*N],ss,sq;

void T(int i)
{int r,k,j;
s[++ss]=i;
if(!v[i])
      v[i]=1;
l[i]=c[i]=d++;
for(j=0;j<w[i];j++)
if(!c[g[i][j]])
      {T(g[i][j]);
      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])
      {k=0,nr++;
      while(ss)
             {r=s[ss--];
             if(r==i||v[r]!=1)
                     break;
             q[++sq]=r,k++,v[r]=2;}
      if(v[i]==1)
             v[i]=2,k++,q[++sq]=i;
      if(!k)
             nr--;
      else
             q[++sq]=0;}}

int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
      scanf("%d%d",&a[i],&b[i]),w[a[i]]++;
for(i=1;i<=n;w[i++]=0)
      g[i]=new int[w[i]];
for(i=1;i<=m;i++)
      g[a[i]][w[a[i]]++]=b[i];
for(i=1;i<=n;i++)
if(!c[i])
      T(i);
printf("%d\n",nr),i=q[sq--];
while(sq)
      {i=q[sq--];
      if(!i)
              printf("\n");
      else
              printf("%d ",i);}
return 0;}