题目：
小兰用七段码数码管来表示一种特殊的文字。
上图显示了七段码数码管的图表，共有数码管7段能发光的二 极管，分别标记为a, b, c, d, e, f, g。
小蓝要选择一部分二极管(至少一个)发光来表达字符。设计字符 所有发光的二极管都需要连接在一起。
例如：bb发光，其他二极管不发光可以用来表达一个字符。
例如cc发光，其他二极管不发光可以用来表达一个字符。该方案与上述方案相匹配 尽管看起来相似，但一行方案可以用来表示不同的字符。
例如：a, b, c, d, ea,b,c,d,e发光，f, gf,g不发光可以用来表达一个字符。
例如：b, fb,f发光，其他二极管不发光，因为发光 二极管没有连成一片。
小蓝能用七段码数码管表达多少种不同的字符？
分析:题目有两个要求:一是至少要求一根管子有亮光，二是亮光管必须连接成一块。
解决方案：要求1，我们使用递归列出所有可能的发光。
void dfs(int d){ use[d]=1；///打开d灯，继续开关下一盏灯 dfs(d 1); use[d]=0.///关闭d灯，继续开关下一盏灯 dfs(d 1); }八个灯管处理完毕后，要判断要求二，发光管是否连成一片。
int find(int x){ //并查集 if(p[x] != x) p[x] = find(p[x]); return p[x]; } void dfs(int d){ if(d==8) { for(int i=1;i<=7;i ) //初始化 p[i]=i; for(int i=1;i<=7;i ) for(int j=1;j<=7;j ) if(e[i][j]&&use[i]&&use[j]) p[find(i)]=find(j); //用并收集将相邻的亮边存储在P集中，根节点是第一边的序号 int k=0; for(int i=1;i<=7;i ) if(use[i] && p[i]==i) k ; if(k==1) ///所有亮边都集中在同一集 ans ; return; } use[d]=1; //打开d这个灯，继续开关下一盏灯 dfs(d 1); use[d]=0; //关闭d这个灯，继续开关下一盏灯 dfs(d 1); } 完整代码：
#include<stdio.h> int ans; int e[10][10],p[10],use[10]; void init() ///连边建图 { e[1][2]=e[1][6]=1; e[2][1]=e[2][7]=e[2][3]=1; e[3][2]=e[3][4]=e[3][7]=1; e[4][3]=e[4][5]=1; e[5][4]=e[5][6]=e[5][7]=1; e[6][1]=e[6][5]=e[6][7]=1; } int find(int x){ //并查集 if(p[x] != x) p[x] = find(p[x]); return p[x]; } void dfs(int d){ if(d==8) { for(int i=1;i<=7;i ) //初始化 p[i]=i; for(int i=1;i<=7;i ) for(int j=1;j<=7;j ) if(e[i][j]&&use[i]&&use[j]) p[find(i)]=find(j); //用并收集将相邻的亮边存储在P集中，根节点是第一边的序号 int k=0; for(int i=1;i<=7;i ) if(use[i] && p[i]==i) k ; if(k==1) ///所有亮边都集中在同一集 ans ; return; } use[d]=1; //打开d这个灯，继续开关下一盏灯 dfs(d 1); use[d]=0; //关闭d这个灯，继续开关下一盏灯 dfs(d 1); } int main() { init(); dfs(1); printf("%d",ans); }答案：80