AOJ : 1015 - Dominating Set

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1015

NP困難として知られている問題らしいです.
詳しくは, 次のページを参照してください.
http://ja.wikipedia.org/wiki/%E6%94%AF%E9%85%8D%E9%9B%86%E5%90%88%E5%95%8F%E9%A1%8C

アルゴリズム

再帰により, 全探索を行いました.
具体的には, ノード1つ1つを, 黒丸にするか白丸にするかを全分岐させて調べました.( O(2^n) )

プログラム

#include <stdio.h>
#include <string.h>

#define MAX 30
#define REP(i,n,m) for(i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int ans,x,y;
int t[MAX][MAX],size[MAX];
int flg[MAX];

int isDomSet(void){
  int i,j;

  rep(i,x){
    if(!flg[i]){
      rep(j,size[i]) if(flg[t[i][j]]) break;
      if(j == size[i]) return 0;
    }
  }

  return 1;
}

void solve(int idx,int cost){
  if(idx == x){
    if(ans > cost && isDomSet()) ans = cost;
    return;
  }

  flg[idx] = 0;
  solve(idx+1,cost);
  flg[idx] = 1;
  solve(idx+1,cost+1);
}

int main(void){
  int i,from,to;

  while(scanf("%d%d",&x,&y) && (x||y)){
    memset(t,0,sizeof(t));
    memset(size,0,sizeof(size));

    rep(i,y){
      scanf("%d%d",&from,&to);
      t[from][size[from]++] = to;
      t[to][size[to]++]= from;
    }

    ans = x;
    solve(0,0);
    printf("%d\n",ans);
  }

  return 0;
}