uva 818 - Cutting Chains(暴力）

題目鏈接：uva 818 - Cutting Chains

題目大意：給出一些環以及那些環之間是相連的，問所最少打開即可環，可以將這些環連成一串，注意不是環。

解題思路：因為n最大才15，可以用一個二進制數表示各個環是否被打開，然後判斷一下是否還有位置度數大於2，以及是否有環的存在。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 20;

int n, ans, k, ti, g[N][N];

void init() {
	ans = n;
	int a, b;
	memset(g, 0, sizeof(g));

	while (scanf("%d%d", &a, &b) == 2) {
		if (a == -1 || b == -1) break;
		g[a-1][b-1] = g[b-1][a-1] = 1;
	}
}

int cal(int s) {
	return s ? cal(s/2) + (s&1) : 0;
}

bool judge() {
	for (int i = 0; i < n; i++) {
		if (k & (1< 2) return true;
	}
	return false;
}

bool dfs(int f, int u, int* vis) {
	if (vis[u]) return true;
	vis[u] = 1;

	for (int i = 0; i < n; i++) {
		if (k & (1<= ti - 1) {
		ans = min(ans, cal(k));
	}
}

int main() {
	int cas = 1;
	while (scanf("%d", &n) == 1 && n) {
		init();
		for (k = 0; k < (1<