蓝桥杯真题-再战七段码--数组全排列&&连通块 || 并查集&&图

原题链接：

2020蓝桥杯省赛C/C++ 七段码 简单易懂的思路_Sh0wMa1ker的博客-CSDN博客_蓝桥杯七段码https://blog.csdn.net/weixin_45783661/article/details/115433100

方法一：数组全排列&&连通块

#include#include#includeusing namespace std;const int N = 100;int e[N][N];int a[N],b[N];int ans;void dfs(int x){b[x] = 0;for(int i =0;i<7;i++){ //搜索下一个节点i if(e[i][x]==1&&b[i]==1){dfs(i);}}}bool check(){for(int i =0;i<7;i++){b[i] = a[i];} int cnt =0;for(int i=0;i<7;i++){if(b[i]){dfs(i);cnt++;}}if(cnt==1)return true;return false;}int main(){//初始化e[0][1] = 1;e[0][5] =1;e[1][0] = 1;e[1][2] = 1;e[1][6] =1;e[2][1] =1;e[2][3] =1;e[2][6] =1;e[3][2] =1;e[3][4] = 1;e[4][3] =1;e[4][5] = 1; e[4][6] =1;e[5][0] =1;e[5][4] =1;e[5][6] =1;e[6][1] = e[6][2] = e[6][4] = e[6][5] =1;for(int i=0;i=i;j--){a[j] = 1;}do{if(check()){ans++;}}while(next_permutation(a,a+7));} cout<<ans<<endl;return 0; } 

方法二：并查集判断连通块（dfs跳出条件一定要加return 不然就无限递归了）

#includeusing namespace std;const int N = 20;int e[N][N];int p[N];//根节点int ans;//答案 int st[N];//灯状态 int find(int x){if(x!=p[x])p[x] = find(p[x]);return p[x];}void dfs(int x){if(x>6){for(int i =0;i<7;i++) p[i] = i;for(int i =0;i<7;i++) {for(int j =0;j < 7;j++){if(e[i][j]&&st[i]&&st[j]){p[find(i)] = find(j);}}}int cnt = 0; for(int i =0;i<7;i++){if(st[i] && p[i] == i){cnt++;}}if(cnt == 1){ans++;}return ;}st[x] = 1;dfs(x+1);st[x] = 0;dfs(x+1);} int main(){//初始化e[0][1] = 1; e[0][5] = 1;e[1][0] = 1; e[1][2] = 1; e[1][6] = 1;e[2][1] = 1; e[2][3] = 1; e[2][6] = 1;e[3][2] = 1; e[3][4] = 1;e[4][3] = 1; e[4][5] = 1; e[4][6] = 1;e[5][0] = 1; e[5][4] =1;e[5][6] =1;e[6][1] = e[6][2] = e[6][4] = e[6][5] =1;dfs(0);cout<<ans<<endl;return 0;}