2020年蓝桥杯C++B组省赛-七段码

题目

题目链接

题解

DFS + 并查集。

哇，不得不说两年前的我确实比现在强，这题是我当年比赛的时候遇到的，当时居然想出来了，现在根本不会，JR老矣，尚能AC否。

1. 用 1 ~ 7 来代表 a ~ g；
2. 若某两个二极管相邻，那么就在它们之间连一条边；
3. 先用 dfs 枚举出二极管的所有亮灭情况；
4. 再用 并查集 判断是否只有一个连通块.

代码

#include
using namespace std;

int vis[10], fa[10], e[10][10];
int ans;

int find (int x) {
	return fa[x] == x ? x : fa[x] = find (fa[x]);
}

void join (int x, int y) {
	int rx = find (x), ry = find (y);
	if (rx!=ry) fa[rx] = ry;
}

void dfs (int x) {
	if (x == 8) {
		int cnt = 0;
		for (int i = 1;i