比赛时想的是二进制枚举和并查集判断是否连通，没有实现。
#include<bits/stdc++.h> using namespace std; int cnt; int a[10][10]; void dfs(int cur) { int t=cur; /*while(t) { cout<<t%2<<' '; t/=2; } cout<<endl;*/ int sum=0; if(cur&1) { sum++; a[1][2]=a[2][1]=1; a[1][3]=a[3][1]=1; } if(cur&2) { sum++; a[2][1]=a[1][2]=1; a[2][4]=a[4][2]=1; a[2][5]=a[5][2]=1; } if(cur&4) { sum++; a[1][3]=a[3][1]=1; a[3][4]=a[4][3]=1; a[3][7]=a[7][3]=1; } if(cur&8) { sum++; a[4][3]=a[3][4]=1; a[4][7]=a[7][4]=1; a[4][2]=a[2][4]=1; a[4][5]=a[5][4]=1; } if(cur&16) { sum++; a[5][4]=a[4][5]=1; a[5][2]=a[2][5]=1; a[5][6]=a[6][5]=1; } if(cur&32) { sum++; a[6][5]=a[5][6]=1; a[6][7]=a[7][6]=1; } if(cur&64) { sum++; a[7][3]=a[3][7]; a[7][4]=a[4][7]; a[7][6]=a[6][7]; } // printf("sum:%d \n",sum); int vis[10]={0}; for(int i=0;i<7;i++) { if(cur&(1<<i)) { vis[i+1]=1; } } for(int i=1;i<=7;i++) for(int j=1;j<=7;j++) for(int k=1;k<=7;k++) { if(a[j][i]&&a[i][k]&&vis[i]&&vis[j]&&vis[k]) a[j][k]=a[k][j]=1; } /*for(int i=1;i<=7;i++) for(int j=1;j<=7;j++) printf("i:%d j:%d %d\n",i,j,a[i][j]); cout<<endl;*/ int all=1; for(int i=1;i<=7;i++) { if(vis[i]) { for(int j=1;j<=7;j++) { if(i!=j&&vis[j]&&a[i][j]) { all++; } } //printf("all:%d sum:%d\n",all,sum); if(all==sum) cnt++; return ; } } } int main() { for(int i=0;i<1<<7;i++) { memset(a,0,sizeof(a)); dfs(i); } printf("%d",cnt); return 0; }