Cod sursa(job #606247)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 august 2011 18:19:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream.h>
#define N 100001
long n,m,w[N],*g[N],k,i,j,t,d,c[N],l[N],nr,a[2*N],b[2*N],u,p,r,v[N],s[2*N],q[2*N],ss,sq;
void tarjan(long i,long *nr,long *d)
{s[++ss]=i,c[i]=(*d),l[i]=(*d)++;
if(!v[i])
      v[i]=1;
for(j=0;j<w[i];j++)
if(!c[g[i][j]])
      {tarjan(g[i][j],nr,d);
      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(ss)
             {r=s[ss--];
             if(r!=i&&v[r]==1)
                     q[++sq]=r,k++,v[r]=2;
             else
                     break;}
      if(v[i]==1)
             v[i]=2,k++,q[++sq]=i;
      if(!k)
             (*nr)--;
      else
             q[++sq]=0;}}
int main()
{ifstream x("ctc.in");
ofstream y("ctc.out");
x>>n>>m;
for(k=1;k<=m;k++)
      x>>a[k]>>b[k],w[a[k]]++;
for(i=1;i<=n;w[i++]=0)
      g[i]=(long*)malloc(w[i]*sizeof(long));
for(j=1;j<=m;j++)
      g[a[j]][w[a[j]]++]=b[j];
for(u=1;u<=n;u++)
if(!c[u])
      tarjan(u,&nr,&d);
y<<nr<<"\n",r=q[sq--];
while(sq)
      {r=q[sq--];
      if(!r)
              y<<"\n";
      else
              y<<r<<" ";}
return 0;}