public class Main { public static int N = 10; public static int e[][] = new int[N][N];// 存储二极管相邻的信息 public static int f[] = new int[N];// 并查集 public static int ans = 0; public static boolean st[] = new boolean[N];// true表示发光 public static void init() { e[1][2] = e[1][6] = 1;// 表示相邻 e[2][1] = e[2][7] = e[2][3] = 1; e[3][2] = e[3][7] = e[3][4] = 1; e[4][3] = e[4][5] = 1; e[5][7] = e[5][6] = e[5][4] = 1; e[6][5] = e[6][7] = e[6][1] = 1; e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1; } public static int find(int u) { if (f[u] == u) return u; f[u] = find(f[u]); return f[u]; } public static void dfs(int d) {// 1-7 if (d > 7) { // 终止条件 for (int i = 1; i <= 7; i++) {// 并查集初始化 f[i] = i; } for (int i = 1; i <= 7; i++) { for (int j = 1; j <= 7; j++) { if (e[i][j] == 1 && st[i] == true && st[j] == true) {// 把所有发光且相邻的二极管合并 int fx = find(i), fy = find(j); if (fx != fy) { f[fx] = fy;// 合并 } } } } int k = 0;// 表示产生的集合的个数 for (int i = 1; i <= 7; i++) { if (st[i] && f[i] == i) k++; } if (k == 1) ans++;// 只产生一个集合,说明所有的发光二极管是连成一片的 return; } st[d] = true; dfs(d + 1); st[d] = false; dfs(d + 1); } public static void main(String[] args) { init(); dfs(1); System.out.println(ans); } }