Problem 1015 : Dominating Set

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

• 問題概要

グラフが与えられる。
ノードを黒と白で塗る。
すべてのノードが

１　隣接するノードのうちひとつ以上が黒いノード
２　自分自身が黒いノード

のどちらかを満たすようなとき、最小の黒の数を求めよ。

• 解法

全探索。
サイズが書いてないから不安だった。

• ソース　

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

class Node{
public:
  bool black;
  vector<int> E;
  Node(){
    black = false;
  }
  bool ok(const vector<Node> &n){
    if(black)return true;
    FOR(it, E){
      if(n[(*it)].black)return true;
    }
    return false;
  }
};

int ans;

inline void search(int now, int cost,  vector<Node> &n){
  if(cost >= ans)return;
  if(now == n.size()){
    bool end = true;
    FOR(it, n)if(!(*it).ok(n))end = false;
    if(end) ans = min(ans, cost);
    return;
  }
  search(now+1, cost, n);
  if(ans == cost)return;
  n[now].black = true;
  search(now+1, cost+1, n);
  n[now].black = false; 
}


main(){
  int N, E;
  while(cin >> N >> E){
    if( N + E == 0)break;
    ans = 1000000000;
    vector<Node> n(N);
    rep(i, E){
      int p1, p2;
      cin >> p1 >> p2;
      n[p1].E.push_back(p2);
      n[p2].E.push_back(p1);
    }
    int now = 0, cost  = 0;
    search(now, cost, n);
    cout << ans << endl;
  }
}