#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=
20;
int g[maxn][maxn];
int vis[maxn];
int n,cnt;
int cacl(
int x)
{
return x==
0?
0:(cacl(x/
2)+(x&
1));
}
bool two(
int x)
//判断是否超过两个联通分量
{
for(
int i=
0;i<n;i++
)
{
if(x&(
1<<i))
continue;
int num=
0;
for(
int j=
0;j<n;j++
)
{
if(x&(
1<<j))
continue;
if(g[i][j]) num++
;
}
if(num>
2)
return 1;
}
return 0;
}
bool dfs(
int x,
int u,
int fa)
{
vis[u]=
1;
for(
int i=
0;i<n;i++
)
if(g[u][i])
{
if(x&(
1<<i)||i==fa)
continue;
if(vis[i])
return 1;
if(dfs(x,i,u))
return 1;
}
return 0;
}
bool cycle(
int x)
//是否成环
{
for(
int i=
0;i<n;i++
)
{
if(vis[i]||x&(
1<<i))
continue;
cnt++;
//不成环的联通分量的个数
if(dfs(x,i,-
1))
return 1;
}
return 0;
}
int solved()
{
int m=(
1<<
n);
int ans=
n;
for(
int i=
0;i<m;i++
)
{
cnt=
0;
memset(vis,0,
sizeof(vis));
if(two(i)||cycle(i))
continue;
int mm=
cacl(i);
if(mm>=cnt-
1)
//打开的环如果比不打开的环个数减一还要大，那么就能连成链
ans=
min(ans,mm);
}
return ans;
}
int main()
{
int Case=
0;
while(~scanf(
"%d",&n)&&
n)
{
memset(g,0,
sizeof(g));
int a,b;
while(~scanf(
"%d%d",&a,&
b))
{
if(a==-
1&&b==-
1)
break;
g[a-
1][b-
1]=g[b-
1][a-
1]=
1;
}
printf("Set %d: Minimum links to open is %d\n",++
Case,solved());
}
return 0;
}
转载于:https://www.cnblogs.com/Wangwanxiang/p/8462834.html
相关资源：数据结构—成绩单生成器
