UVA-818 dfs + 位运算

暴力枚举一些圆环，将这些圆环解开，看能否成为单链。判断单链的三个条件：

1. 除了这些删除的圆环之外，其他圆环还连接着的圆环不能超过两个。
2. 剩下的环没有连成圈。
3. 剩下的圆环共分成m堆，每堆之间无连接，m必须小于等于解开的圆环数+1。

最多有15个环，可以用二进制保存。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define pos(x) (1 << ((x) - 1))
const int maxn = 20;
int g[maxn], vis[maxn], d[maxn];
int n;

int bit(int x) {
	int cnt = 0;
	while(x > 0) {
		if(x & 1) ++cnt;
		x >>= 1;
	}
	return cnt;
}

bool dfs(int u, int pre){
	vis[u] = -1;
	int m = g[u];
	for(int i = 1; i <= n; ++i){
		if(d[i] || i == pre || !(pos(i) & m)) continue;
		if(vis[i] == -1) return false;
		if(!vis[i] && !dfs(i, u)) return false;
	}
	vis[u] = 1;
	return true;
}

bool solve(int p){
	memset(vis, 0, sizeof(vis));
	memset(d, 0, sizeof(d));
	for(int i = 1; i <= n; ++i){
		if(pos(i) & p) d[i] = 1;
	}

	for(int i = 1; i <= n; ++i) {
		if(d[i]) continue;
		int x = 0;
		for(int j = 1; j <= n; ++j){
			if(!d[j] && pos(j) & g[i]) ++x;
		}
		if(x > 2) return false;
	}

	int cnt = 0; //联通块数量
	for(int i = 1; i <= n; ++i){
		if(vis[i] || d[i]) continue;
		if(!dfs(i, -1)) return false;  //有环
		++cnt;
	}
	if(cnt > bit(p) + 1) return false;  //大于独立的圆环数，无法连接
	return true;

}

int main() {
	int kase = 0;
	while(scanf("%d", &n) == 1 && n){
		int a, b;
		memset(g, 0, sizeof(g));
		while(1) {
			scanf("%d%d", &a, &b);
			if(a == -1 && b == -1) break;
			g[a] |= (1 << (b - 1)); //a can reach b
			g[b] |= (1 << (a - 1)); //b can reach a
		}
		int total = 1 << n;
		int ans = 1 << 30;
		for(int i = 0; i < total; ++i) {
			if(bit(i) >= ans) continue;
			if(solve(i)) {
				ans =min(ans, bit(i));
			}
		}
		printf("Set %d: Minimum links to open is %d\n", ++kase, ans);
	}
	return 0;
} 

如有不当之处欢迎指出！