medium-codechef-RRSERVER-1.c

#include <stdio.h>
#include <string.h>
#define MIN(a,b) (((a)<(b))?(a):(b))

int getBit(long long int s, int i) {
  return (s >> i) & 1;
}

long long int clearBit(long long int s, int i) {
    s ^= 1 << i;
    return s;
}

unsigned int countSetBits(int n) 
{ 
    unsigned int count = 0; 
    while (n) 
    { 
      n &= (n-1) ; 
      count++; 
    } 
    return count; 
}

int main(void) {
    // your code goes here
    int n, m, i, k;
    scanf("%d %d", &n, &m);
    int a, b;
    int connection, diff, count, required;
    long long int conn[n];
    short f[(1<<n)+10];
    short dp[(1<<n)+10];

    for (int t=0;t<n;t++) {
        conn[t] = 0;
    }
    for(int i=0; i<m; ++i) {
        scanf("%d %d", &a, &b);
        conn[a-1] = clearBit(conn[a-1], b-1);
        conn[b-1] = clearBit(conn[b-1], a-1);
    }
    for (long long int k=0;k<((1<<n)+10);++k) {
        f[k] = 1e4;
        int t_cost = 0;
        for(i=0;i<n;i++) {
            if (getBit(k, i)) {
                connection = conn[i];
                diff = connection & k;
                count = countSetBits(diff);
                required = countSetBits(connection) - count;
                t_cost += required;
            }
        }
        dp[k] = t_cost;
    }
    f[0] = 0;
    long long int cleared;
    for(long long int s=1;s<(1<<n);++s) {
        for (i=0;i<n;++i) {
            if (getBit(s, i)) {
                cleared = clearBit(s, i);
                f[s] = MIN(f[s], f[cleared]+dp[cleared]);
            }
        }
    }
    printf("%lld\n", f[(1<<n)-1]);
    return 0;
}