#include<stdio.h>
#include<stdlib.h>
typedef unsigned int bool;
typedef int sommet;
#define N 30000
#define A 64000
typedef bool gr1[N][N];
typedef struct maillon maillon, *liste;
struct maillon {sommet s; liste suiv;};
typedef liste gr2[N];
typedef struct{sommet ori,ext;} arc, gr3[A];
typedef int ts3[N+A];
void affgr1(gr1 g1)
{ int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) if(g1[i][j]) printf(" %d-->%d ",i,j);
  printf("\n");
}
void affgr3(gr3 g3)
{ int k;
  for(k=0;k<A;k++) printf(" %d-->%d ",g3[k].ori,g3[k].ext);
  printf("\n");
}
void gr1gr3(gr1 g1,gr3 g3)
{ int i,j,k=0;
  for(i=0;i<N;i++) for(j=0;j<N;j++) if(g1[i][j]) g3[k++]=(arc){i,j};
}
void gr3gr1(gr3 g3,gr1 g1)
{ int i,j,k;
  for(i=0;i<N;i++) for(j=0;j<N;j++) g1[i][j]=0;
  for(k=0;k<A;k++) g1[g3[k].ori][g3[k].ext]=1;
}
void set1gr3(gr3 g3)
{ int i,j,ij,k=0;
  for(i=0;i<N;i++) for(j=0;j<=i;j++) if(ij=i*j%N,(i+j+ij+ij*ij)%N==0)
  { if(        k++<A) g3[k-1]=(arc){i,j};
    if(i!=j && k++<A) g3[k-1]=(arc){j,i};
  }
  printf("A=%d k=%d\n",A,k);
  if(k!=A) exit(1);
}
void set2gr3(gr3 g3)
{ int i,i2,j,ij,s,d,k=0,tete[N],suiv[N];
  for(i=0;i<N;i++) tete[i]=-1;
  for(j=0;j<N;j++) suiv[j]=tete[i=j*j%N], tete[i]=j;
  for(ij=0;ij<N;ij++)
  for(d=tete[s=ij*(N+~ij)%N,(s*s-4*ij+4*N)%N];d>=0;d=suiv[d])
  for(i2=(s+d)%N;i2<2*N;i2+=N) if(1&~i2) if(i=i2/2, j=(s-i+N)%N, i*j%N==ij)
  if(k++<A) g3[k-1]=(arc){i,j};
  printf("A=%d k=%d\n",A,k);
  if(k!=A) exit(1);
}
void gr3ts3(gr3 g3,ts3 tete)
{ int *suiv=tete+N, i, k;
  for(i=0;i<N;i++) tete[i]=-1;
  for(k=0;k<A;k++) suiv[k]=tete[i=g3[k].ori], tete[i]=k;
}
int nbcc(gr3 g3,int cc[N])
{ ts3 tete;
  int nbc=-1, *suiv=tete+N, pile[N], ip=0, i, j, k;
  gr3ts3(g3,tete);
  for(i=0;i<N;i++) cc[i]=-1;
  for(i=0;i<N;i++) if(cc[i]<0) for(cc[pile[ip++]=i]=++nbc;ip;)
  for(k=tete[pile[--ip]];k>=0;k=suiv[k]) if(cc[j=g3[k].ext]<0) cc[pile[ip++]=j]=nbc;
  return nbc+1;
}
int main()
{ gr3 g3;
  int cc[N], i ,j;
  set1gr3(g3); //affgr3(g3);
  set2gr3(g3); //affgr3(g3);
  //{gr1 g1; gr3gr1(g3,g1); affgr1(g1);}
  printf("Il y a %d composantes connexes.\nLa composante de 1 contient :",nbcc(g3,cc));
  for(i=j=0;i<N;i++) if(cc[i]==cc[1]) j++, printf(" %d",i);
  printf("\nElle a %d éléments.\n",j);
  return 0;
}