蓝桥杯-分考场

DFS + 回溯 + 图


import os
import sys

# 请在此输入您的代码
n = int(input())
m = int(input())

# 人
g = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a][b] = g[b][a] = 1

color = [0] * (n + 1)

# 最多一人一个考场，每次都尝试选一个最小的答案
ans = n

# 第 i 个人能否在 c 考场
def check(i, c):
    for j in range(1, n + 1):
        # i 认识 j 而且 j 的考场与 i 预选的考场一致
        if g[i][j] and color[j] == c:
            return False
    return True

def dfs(i, used):
    global ans

    if used >= ans:
        return

    # 分完了
    if i > n:
        ans = min(ans, used)
        return

    for c in range(1, used + 1):
        # 尝试将 i 分配到 c 考场
        if check(i, c):
            # 将 i 分配到 c 考场
            color[i] = c
            # 递归
            dfs(i + 1, used)
            # 回溯
            color[i] = 0
    # 新开考场
    color[i] = used + 1
    dfs(i + 1, used + 1)
    color[i] = 0
dfs(1, 0)
print(ans)