08 魔女填色游戏（图染色问题）

题目描述

给定一个无向图，每个结点已有颜色（蓝色 0 或红色 1）。要求相邻结点颜色不同，求最少需要修改多少个结点的颜色。若无法满足要求，输出 “Impossible”。

问题分析

核心性质

题目要求「任意结点与和它直接相连的所有结点颜色不同」，这正是二分图的定义：

• 二分图的顶点集可以分割为两个互不相交的子集
• 图中每条边连接的两个顶点属于不同的子集

因此问题转化为：

1. 判断图是否为二分图
2. 若是二分图，求最小修改次数

解题思路

二分图判定

使用 BFS/DFS 进行染色的同时检测冲突：

• 从任意未访问节点开始，染成颜色 0
• 相邻节点必须染成不同颜色
• 若发现相邻节点同色，则图不是二分图

最小修改次数

对于每个连通分量，假设最终颜色分配为 $(A, B)$ 两个集合：

• 方案一：集合 A 为蓝色 (0)，集合 B 为红色 (1)

  • 需修改的节点数 = 集合 A 中原色为红色的 + 集合 B 中原色为蓝色的

• 方案二：集合 A 为红色 (1)，集合 B 为蓝色 (0)

  • 需修改的节点数 = 集合 A 中原色为蓝色的 + 集合 B 中原色为红色的

取两种方案的较小值即可。

正确性证明

引理1：若图是二分图，则存在一种染色方案使得相邻节点颜色不同。

证明：二分图定义即是如此。$\square$

引理2：在连通分量中，若确定了一端的颜色，另一端颜色随之确定。

证明：从任意节点开始 BFS/DFS，相邻节点必须异色，依次传递，整个连通分量只有两种可能的染色方案。$\square$

定理：算法得到的最小修改次数是最优解。

证明：对于每个连通分量，根据引理2只有两种合法染色方案。枚举这两种方案，取修改次数较少者，即为该分量的最优解。所有连通分量独立，求和即为全局最优。$\square$

代码实现

BFS 版本

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
c = [int(x) for x in input().split()]
adj = [[] for _ in range(n)]

for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

visited = [-1] * n  # -1: 未访问, 0/1: 染色结果
ans = 0

for i in range(n):
    if visited[i] != -1:
        continue

    q = deque([i])
    visited[i] = 0
    res = [0, 0]  # res[0]: 以0为基准的修改次数, res[1]: 以1为基准的修改次数

    while q:
        u = q.popleft()
        # 计算两种基准下的修改次数
        res[0] += visited[u] ^ c[u]       # 若最终为0，需要修改多少次
        res[1] += (visited[u] ^ 1) ^ c[u] # 若最终为1，需要修改多少次

        for v in adj[u]:
            if visited[v] == -1:
                q.append(v)
                visited[v] = visited[u] ^ 1
            elif visited[v] == visited[u]:
                print("Impossible")
                exit()

    ans += min(res)

print(ans)

DFS 版本（递归）

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
node = list(map(int, input().split()))

adj = [[] for _ in range(n)]
for _ in range(n):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

vis = [-1] * n

def dfs(u, c):
    vis[u] = c
    cnt = (vis[u] != node[u])  # 当前颜色与node[u]不匹配的个数
    total = 1
    for v in adj[u]:
        if vis[v] == c:
            return False, 0, 0
        if vis[v] == -1:
            ok, cc, tot = dfs(v, 1 ^ c)
            if not ok:
                return False, 0, 0
            cnt += cc
            total += tot
    return True, cnt, total

ans = 0
for u in range(n):
    if vis[u] == -1:
        ok, c, tot = dfs(u, 0)
        if not ok:
            print("Impossible")
            exit()
        ans += min(c, tot - c)

print(ans)

复杂度分析

• 时间复杂度：$O(n + m)$，每个节点和边访问常数次
• 空间复杂度：$O(n + m)$，邻接表和染色数组

关键点总结

概念	说明
二分图判定	BFS/DFS 染色，相邻异色
冲突检测	发现相邻同色 → Impossible
最小修改	枚举两种染色方案，取较小值