1015-Dominating Set

英文読解が大変。
英語版Wikipediaに助けられました。
dfsで全探索する。
計算量はO(2^y)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_V=30;
int V;
char g[MAX_V][MAX_V];
int memo[MAX_V];
int a,b,y;
int ans;
void dfs(int used,int covered,int now,int k){
	if(ans<=now)return;
	if(covered==(1<<V)-1){
		ans=min(ans,now);return;
	}
	int t;
	for(int i=k;i<V;i++){
		if((used&(1<<i))==0){
			t=covered;
			t|=memo[i];
			dfs(used|(1<<i),t|(1<<i),now+1,i+1);
		}
	}
}
int main() {
	for(;;){
		cin >> V >> y;if(V==0&&y==0)break;
		memset(g,0,sizeof(g));
		if(V>MAX_V)return -1;
		for(int i=0;i<y;i++){
			cin >> a >> b;
			g[a][b]=1;g[b][a]=1;
		}
		for(int i=0;i<V;i++){
			int t=0;
			for(int j=0;j<V;j++){
				if(g[i][j]==1){
					t|=1<<j;
				}
			}
			memo[i]=t;
		}
		ans=9999;
		dfs(0,0,0,0);
		cout << ans << endl;
	}
	return 0;
}