#include<stdio.h>
enum {A,B,C,D,E,F,G,H,I,J,K};
void affg1(int nv, int g[nv][nv])
{ int s,t;
  for(s=0;s<nv;s++)
  for(t=0;t<nv;t++)
  if(g[s][t])
  printf(" %c->%c",s+'A',t+'A');
  printf("\n");
}
void affg2(int ne, int g[2*ne])
{ int k;
  for(k=0;k<2*ne;k+=2)
  printf(" %c->%c",g[k]+'A',g[k+1]+'A');
  printf("\n");
}
void affg3(int nv, int t[], int lim[])
{ int s,k;
  for(s=0;s<nv;s++)
  for(k=lim[s];k<lim[s+1];k++)
  printf(" %c->%c",s+'A',t[k]+'A');
  printf("\n");
}
void g2g3(int nv, int ne, int g2[], int t[], int lim[])
{ int i, degre[nv];
  for(i=0;i<nv;i++) degre[i]=0;
  for(i=0;i<ne;i++) degre[g2[2*i]]++;
  lim[0]=0;
  for(i=1;i<=nv;i++) lim[i]=lim[i-1]+degre[i-1];
  for(i=0;i<nv;i++) degre[i]=lim[i];
  for(i=0;i<2*ne;i+=2)   t[degre[g2[i]]++]=g2[i+1];
}
int g1g2(int nv,int g1[nv][nv],int g2[])
{ int i, j, k=0;
  for(i=0;i<nv;i++)
  for(j=0;j<nv;j++) if(g1[i][j])
  { g2[k++]=i; g2[k++]=j; }
  return k/2; // nombre d'arcs
}
void g2g1(int nv,int ne,int g2[],int g1[nv][nv])
{ int i, j, k;
  for(i=0;i<nv;i++)
  for(j=0;j<nv;j++) g1[i][j]=0;
  for(k=0;k<2*ne;k+=2) g1[g2[k]][g2[k+1]]=1;
}
void g3g1(int nv,int t[],int lim[],int g1[nv][nv])
{ int i, j, k;
  for(i=0;i<nv;i++)
  for(j=0;j<nv;j++) g1[i][j]=0;
  for(i=0;i<nv;i++)
  for(k=lim[i];k<lim[i+1];k++) g1[i][t[k]]=1;
}
int g3g2(int nv,int t[],int lim[],int g2[])
{ int i, j=0, k;
  for(i=0;i<nv;i++)
  for(k=lim[i];k<lim[i+1];k++)
  { g2[j++]=i; g2[j++]=t[k]; }
  return j/2;
}
void g1g3(int nv,int ne,int g1[nv][nv],int t[],int lim[])
{ int g2[2*ne];
  g1g2(nv,g1,g2);
  g2g3(nv,ne,g2,t,lim);
}
int cherchecc1(int nv,int g[nv][nv],int cc[nv])
{ int ncc=0;                           // nombre de composantes connexes déjà trouvées
  void dfs(int s)
  { cc[s]=ncc;
    for(int t=0;t<nv;t++) if(g[s][t])  // tout sommet t voisin de s
    if(cc[t]==-1) dfs(t);              // non encore visité va l'être
  }
  for(int s=0;s<nv;s++) cc[s]=-1;      // Aucun sommet n'a encore été visité.
  for(int s=0;s<nv;s++) if(cc[s]==-1)  // Tout sommet non encore visité
  { ncc++; dfs(s); }                   // est le premier sommet d'une nouvelle composante connexe.
  return ncc;                          // nombre total de composantes connexes
}
int cherchecc3(int nv,int t[],int lim[],int cc[nv])
{ int ncc=0;
  void dfs(int s)
  { cc[s]=ncc;
  //for(int t=0;t<nv;t++) if(g[s][t])
    for(int u,k=lim[s];k<lim[s+1];k++) // tout sommet u=t[k] voisin de s
    if(cc[u=t[k]]==-1) dfs(u);
  }
  for(int s=0;s<nv;s++) cc[s]=-1;
  for(int s=0;s<nv;s++) if(cc[s]==-1)
  { ncc++; dfs(s); }
  return ncc;
}
void g1g1n(int nv,int g[nv][nv],int f[nv][nv])
{ int i,j;
  for(i=0;i<nv;i++)
  for(j=0;j<nv;j++) f[i][j]=g[i][j];
  for(i=0;i<nv;i++)
  for(j=0;j<nv;j++) if(g[i][j]) f[j][i]=1;
}
int g2g2n(int ne,int g[],int h[])
{ for(int k=0;k<2*ne;k+=2)
  { h[2*ne+k]=h[k+1]=g[k+1];
    h[2*ne+k+1]=h[k]=g[k];
  }
  return 2*ne;
}
void afft(int t[],int n)
{ while(n--) printf("%d ",*t++);
}
#define AFFT(t,n) printf(#t" : "),afft(t,n),printf("\n")
void testcc1(int nv,int g[nv][nv])
{ int h[nv][nv], cc[nv];
  printf("testcc1 nv=%d\n",nv);
  affg1(nv,g);
  g1g1n(nv,g,h);
  affg1(nv,h);
  cherchecc1(nv,h,cc);
  AFFT(cc,nv);
  printf("testcc1 fin\n");
}
void testcc2(int nv,int ne,int g2[2*ne])
{ int t[4*ne], lim[nv+1], h2[4*ne], cc[nv];
  printf("testcc2 nv=%d\n",nv);
  affg2(ne,g2);
  g2g2n(ne,g2,h2);
  affg2(2*ne,h2);
  g2g3(nv,ne*2,h2,t,lim);
  affg3(nv,t,lim);
  cherchecc3(nv,t,lim,cc);
  AFFT(cc,nv);
  printf("testcc2 fin\n");
}
void testcc()
{ int nv=11, ne=13, g1[nv][nv],
      g2[]={A,B, B,A, C,B, F,C, F,B,
            F,G, G,K, K,J, J,F, D,E,
            D,H, E,H, I,E};
  g2g1(nv,ne,g2,g1);
  testcc1(nv,g1);
  testcc2(nv,ne,g2);
}
int main()
{ int nv=4, ne=6, g2[]={A,B, B,C, C,D, D,A, D,B, A,C},
  g1[][4]={{0,1,1,0},
           {0,0,1,0},
           {0,0,0,1},
           {1,1,0,0}},
  t[]={B,C,  C,  D,  A,B}, lim[]={0,2,3,4,6};
  int f1[][3]={{0,1,0},{0,0,1},{0,0,0}};
  int f2[]={A,B, B,C}, nv2=3, ne2=2;
  affg1(nv,g1);
  affg2(ne,g2);
  affg3(nv,t,lim);
  
  affg1(nv2,f1);
  affg2(ne2,f2);
  g2g3(nv2,ne2,f2,t,lim);
  affg3(nv2,t,lim);
  
  g2g3(nv,ne,g2,t,lim);
  affg3(nv,t,lim);
  { int g2[ne*2];       g1g2(nv,g1,g2);      affg2(ne,g2); }
  { int g1[nv][nv];     g2g1(nv,ne,g2,g1);   affg1(nv,g1); }
  { int g1[nv][nv];     g3g1(nv,t,lim,g1);   affg1(nv,g1); }
  { int g2[ne*2];       g3g2(nv,t,lim,g2);   affg2(ne,g2); }
  { int t[ne],lim[nv+1];g1g3(nv,ne,g1,t,lim);affg3(nv,t,lim);}
  { int t[ne],lim[nv+1];g2g3(nv,ne,g2,t,lim);affg3(nv,t,lim);}
  testcc1(nv,g1);
  testcc();
  getchar();
  return 0;
}