Skip to main content
8 of 22
Rollback to Revision 6
ceilingcat
  • 7.7k
  • 2
  • 30
  • 30

C (gcc), 790 778 757 bytes

typedef struct F F;typedef struct{int c;int p;F**m;}g;struct F{int d;g f;};g S,y,q,*x=&y,*p=&q;A(g*g,F*s){g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;}F*B(d){F*s=0;for(int i=S.c;i--;)s=S.m[i]->d-d?s:S.m[i];!s?s=calloc(5,4),s->d=d,A(&S,s):0;return s;}E(g**c,g**p){int*t,i=-1,b,j,k,l;g*z=*c,*y=*p;for(;b=++i<S.c;b&&A(z,S.m[i]))for(l=0;k=l<z->c&b;b&=!k)for(F*p=z->m[(j=0)+l++];j<p->f.c&&(k=p->f.m[j++]->d-S.m[i]->d););z->c>y->c?y->c=0,t=z,*c=y,*p=t:(z->c=0);}i,*a,c[9999],L[999];main(b){for(F*u,*v;gets(L)&&(sscanf(L,"%d %d",&a,&b)>1?u=B(a),A(&u->f,v=B(b)),A(&v->f,u),1:0););for(E(&x,&p);b=i<S.c;)c[i]<i?a=S.m[b=i%2*c[i]++],S.m[b]=S.m[i],S.m[i]=a,E(&x,&p),i=0:(c[i++]=0);for(printf("largest clique size: %d\nclique members:",p->c);b<p->c;)printf(" %d",p->m[b++]->d);}

This is a slightly golfed version of the reference implementation. Try it online!

Slightly golfed less

typedef struct F F;
// student group
typedef struct{
  int c; // count
  int p; // capacity
  F**m;  // members
}g;
// student
struct F{
  int d; // id
  g f;   // friends
};
g S,y,q,*x=&y,*p=&q;
A(g*g,F*s){
  g->c++[g->m=g->c-g->p?g->m:realloc(g->m,(g->p+=32)*20)]=s;
}
F*B(d){
  F*s=0;
  for(int i=S.c;i--;)
    s=S.m[i]->d-d?
      s
    :
      S.m[i];
  !s?
    s=calloc(5,4),
    s->d=d,A(&S,s)
  :
    0;
  return s;
}
E(g**c,g**p){
  int*t,i=-1,b,j,k,l;
  g*z=*c,*y=*p;
  for(;b=++i<S.c;b&&A(z,S.m[i]))
    for(l=0;k=l<z->c&b;b&=!k)
      for(F*p=z->m[(j=0)+l++];j<p->f.c&&(k=p->f.m[j++]->d-S.m[i]->d););
  z->c>y->c?
    y->c=0,
    t=z,
    *c=y,
    *p=t
  :
    (z->c=0);
}
i,*a,c[9999];
main(b){
  for(F*u,*v;scanf("%d %d",&a,&b)>1?u=B(a),A(&u->f,v=B(b)),A(&v->f,u),1:0;)
  for(E(&x,&p);b=i<S.c;)
    c[i]<i?
      a=S.m[b=i%2*c[i]++],
      S.m[b]=S.m[i],
      S.m[i]=a,
      E(&x,&p),
      i=0
    :
      (c[i++]=0);
  for(printf("largest clique size: %d\nclique members:",p->c);b<p->c;)
    printf(" %d",p->m[b++]->d);
}
ceilingcat
  • 7.7k
  • 2
  • 30
  • 30