杰人编程网

def count_coloring_schemes(M, N, edges):
    from collections import defaultdict

    # 构建邻接表
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # 回溯函数
    def backtrack(node, color, color_assignment):
        if node > M:
            return 1
        total = 0
        for c in [0, 1]:  # 0: 黑色, 1: 红色
            if c == 1:  # 如果是红色，检查相邻节点是否也是红色
                if any(color_assignment[neighbor] == 1 for neighbor in graph[node]):
                    continue
            color_assignment[node] = c
            total += backtrack(node + 1, c, color_assignment)
            color_assignment[node] = -1
        return total

    # 初始化颜色分配
    color_assignment = {i: -1 for i in range(1, M + 1)}
    return backtrack(1, -1, color_assignment)

# 输入处理
M = int(input("请输入节点数: "))
N = int(input("请输入边数:" ))
edges = []
for _ in range(N):
    u, v = map(int, input().split())
    edges.append((u, v))

# 计算染色方案数
result = count_coloring_schemes(M, N, edges)

# 输出结果
print(result)