一、题目描述
给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
二、输入输出描述
输入描述
- 第一行：两个整数 M（节点数，1 ≤ M ≤ 15）、N（边数，0 ≤ N ≤ M×3）；
- 后续 N 行：每行两个整数 V1、V2，表示 V1 和 V2 之间存在一条无向边（节点编号默认从 0/1 开始，需统一处理）；
备注：图中节点不一定连通，边为无向边。
输出描述
- 一个整数，表示符合约束的染色方案总数。
三、示例
| 输入 |
4 4 |
| 输出 | 7 |
| 说明 |
4个节点，4条边，1号节点和2号节点相连， 2号节点和4号节点相连，3号节点和4号节点相连， 1号节点和3号节点相连， 若想必须保证相邻两个节点不能同时为红色，总共7种方案。 |
| 输入 |
3 3 |
| 输出 | 4 |
| 说明 |
|
| 输入 |
4 3 |
| 输出 | 8 |
| 说明 |
|
四、解题思路
1. 核心思想
采用DFS + 回溯 + 剪枝的策略，枚举所有可能的红色节点子集，通过「邻接表快速判断相邻」和「按顺序枚举避免重复」，剪枝掉 “红色节点相邻” 的非法子集，最终统计所有合法染色方案数。核心是 “枚举不重复、剪枝提效率、回溯复状态”。
2. 问题本质分析
- 表层问题：统计无向图中「红色节点互不相邻」的染色方案数；
- 深层问题：
3. 核心逻辑
- 图的构建：用邻接表存储每个节点的邻居，支持快速相邻判断；
- 初始计数：默认全黑方案（count=1）；
- DFS 枚举：从节点 1 开始，按升序枚举每个节点是否选作红色；
- 剪枝规则：若当前节点与已选红色节点相邻，跳过该节点；
- 计数更新：合法节点选作红色时，计数 + 1；
- 回溯恢复：递归后移除当前节点的邻居集合，恢复 path 状态，继续枚举下一分支。
4. 步骤拆解
图的构建
- 读取节点数、边数、所有边，构建无向图的邻接表（每个节点对应其邻居集合）。
DFS 初始化
- 启动 DFS，参数：邻接表、节点总数 m、起始枚举节点 index=1、初始计数 count=1（全黑方案）、空 path（无红色节点）。
DFS 枚举与剪枝
- 循环枚举节点 i（从 index 到 m）：
- 若 i 有邻居：将其邻居集合加入 path，递归枚举 i+1 开始的节点；
- 若 i 无邻居：直接递归枚举 i+1 开始的节点；
结果返回
- 枚举完所有节点后，返回最终 count，即为合法方案总数。
五、代码实现
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] edges = new int[n][2];
for (int i = 0; i < n; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
}
System.out.println(getResult(edges, m));
}
/**
* @param edges 边，即[v1, v2]
* @param m 点数量
* @return
*/
public static int getResult(int[][] edges, int m) {
// connect用于存放每个节点的相邻节点
HashMap<Integer, HashSet<Integer>> connect = new HashMap<>();
for (int[] edge : edges) {
connect.putIfAbsent(edge[0], new HashSet<>());
connect.get(edge[0]).add(edge[1]);
connect.putIfAbsent(edge[1], new HashSet<>());
connect.get(edge[1]).add(edge[0]);
}
// 节点从index=1开始，必有count=1个的全黑染色方案
return dfs(connect, m, 1, 1, new LinkedList<>());
}
// 该方法用于求解给定多个节点染红的全组合数
public static int dfs(
HashMap<Integer, HashSet<Integer>> connect,
int m,
int index,
int count,
LinkedList<HashSet<Integer>> path) {
if (path.size() == m) return count;
outer:
for (int i = index; i <= m; i++) {
// 如果新加入节点i和已有节点j相邻，则说明新加入节点不能染成红色，需要进行剪枝
for (HashSet<Integer> p : path) {
if (p.contains(i)) continue outer;
}
count++;
if (connect.containsKey(i)) {
path.addLast(connect.get(i));
count = dfs(connect, m, i + 1, count, path);
path.removeLast();
} else {
count = dfs(connect, m, i + 1, count, path);
}
}
return count;
}
}
