题目： 有n个圆环，其中有一些已经扣在一起了，现在需要打开尽量少的圆环，使得所有的圆环可以组成一条链（当然，所有打开的圆环最后都要再次闭合）。例如，有5个圆环，1-2，2-3，4-5 则需要打开一个圆环4，这样用它穿过3和5 这样就连成1-2-3-4-5
要点；
首先得搞明白这个圆环是如何插的，可以想象一下，把4这个圆环从 4-5这个链接中断开后， 4 和 5都是独立的圆环，而一个圆环在插入的时候，事实上是可以链接两条链的，他可以链接 1-2-3 这条原有的链 和 5这条链，因此 如果题目是 给出15个圆环但初始不给任何的链接，那么至少需要7次断开和链接 ，比如 2 链接在 1链和 3链之间，这是题目要搞懂的意思。
另外，采用二进制枚举的方式，枚举的到底是链是否断开，还是节点是否断开，这也是需要考虑的问题，以下代码枚举的是节点打开的状态，意思是 例如 1-2 2-3 4-5 我们枚举 1节点断开 其他节点不断开 用 00001 表示 则 00011 表示1和2节点都断开，依次类推。
需要注意的是 如果断开后 仍然出现一个节点的分支数大于2的情况，那么不可能称为一条单链，例如 1-2 1-3 1-4 1-5 这个时候断开5
变成 1-2 1-3 1-4 和 5一条单链 由于1链接2，3，4 则不可能链接成一条单链 如若是 1-2 1-3 1-4 断开4 1-2 1-3 4 那么原有的链看成 2-1-3
4插入最左和最右都可以另外还要判环，如果断开节点后仍然成环，那么也是不可以的。
最后还要判断现有的链数和断开节点的关系 如果现有的链数为 3 那么至少需要两个断开的节点才能将这个链子连起来。因此要保证断开的节点个数 >= 链数 - 1
说的有些啰嗦，因为本人在做这道题的时候，网上很多都没解释清楚，直接扔代码，导致本人也想了挺久的。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 15 + 5;
int n;
int G[maxn][maxn];
int vis[maxn];
int line;
bool two(int s) {
for(int i = 0; i < n; i++) {
if((s >> i) & 1) continue; //该节点已被打开 等待插环
int cnt = 0;
for(int j = 0; j < n; j++) {
if((s >> j) & 1) continue;
if(G[i][j]) cnt++;
}
if(cnt > 2) return true;
}
return false;
}
bool dfs(int now, int s, int fa) {
vis[now] = -1; //正在访问
for(int i = 0; i < n; i++) {
if(((s >> i) & 1) || !G[now][i] || i == fa) continue; //无视断开的点
if(vis[i]) return true; //又走回来了
if(dfs(i, s, now)) return true;
}
vis[now] = 1; //访问完毕
return false;
}
bool circle(int s) {
line = 0; //残留的链数
for(int i = 0; i < n; i++) {
if((s >> i) & 1) continue;
if(vis[i]) continue;
if(dfs(i, s, -1))
return true;
line++;
}
return false;
}
int cal(int s) {
return s == 0 ? 0 : cal(s / 2) + (s & 1);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int kase = 0;
while(cin >> n && n) {
memset(G, 0, sizeof(G));
int a, b;
while(cin >> a >> b && a != -1) {
G[a - 1][b - 1] = G[b - 1][a - 1] = 1;
}
int s = (1 << n);
//二进制枚举哪些节点需要打开
int ans = maxn;
for(int i = 0; i < s; i++) {
memset(vis, 0, sizeof(vis));
if(two(i)) continue;
if(circle(i)) continue;
//节点数小于链数的话，连不起来
if(cal(i) >= line - 1) {
ans = min(ans, cal(i));
}
}
//Set 1: Minimum links to open is 6
cout << "Set " << ++ kase << ": Minimum links to open is " << ans << endl;
}
return 0;
}