题目：Cutting Chains
思路：用二进制枚举打开的圈，把这些圈打开后，将其它没有打开的圈重新构成一张新图。如果这张新图中有环或有分叉，或者是连通块的个数n减1比打开的圈数还大，则不可行。
判环的方法类似拓扑排序，判断有无分叉的方法是，如果有一个点的度数大于等于3，那么有分叉。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
#include<queue>
#include<set>
using namespace std;#define maxn 15int n;
int a[maxn+5][maxn+5];
int g[maxn+5][maxn+5];
int num=0;
bool Fill[maxn+5];void init(){memset(a,0,sizeof(a));memset(Fill,0,sizeof(Fill));num=0;int x,y;while(~scanf("%d%d",&x,&y)&&x!=-1&&y!=-1){if(x!=y) a[x][y]=a[y][x]=true;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][0]+=a[i][j];}}
}void make(int x){int k=0;num=0;while(x){k++;bool y=x%2;x/=2;if(y){num++;for(int i=1;i<=n;i++)if(g[k][i]){g[i][k]=0;g[k][i]=0;g[i][0]--;g[k][0]--;}}}
}bool find(){for(int i=1;i<=n;i++){if(g[i][0]>2) return false;}bool use[maxn+5]={0};int flag=0;int x=0;do{flag=0;for(int i=1;i<=n;i++)if(!use[i]&&(g[i][0]==0||g[i][0]==1)){use[i]=true;x++;flag=true;for(int j=1;j<=n;j++){if(g[j][i]){g[j][0]--;}}}}while(flag);if(x==n) return true;return false;
}void dfs(int x){Fill[x]=true;for(int i=1;i<=n;i++){if(g[x][i]&&!Fill[i]) dfs(i);}
}int main() {int T=0;while(~scanf("%d",&n)&&n!=0){init();int s=maxn;for(int i=0;i<(1<<n);i++){memcpy(g,a,sizeof(a));memset(Fill,0,sizeof(Fill));make(i);int m=0;for(int j=1;j<=n;j++){if(!Fill[j]){m++;dfs(j);}}if(num>=m-num-1&&find()){s=min(s,num);}}printf("Set %d: Minimum links to open is %d\n",++T,s);}return 0;
}