第 93 章　拓扑排序与二分图

配套例题：BISHI100 【模板】二分图结构Ⅰ-A ‖ 染色判定、BISHI38 有向二分图构造 来源：S3 day7 简单图论；S4 模板.docx「图 → 拓扑排序（以洛谷旅行计划为例）」 前置：90-图的表示与遍历、33-队列与双端队列、38-并查集、35-优先队列与堆

这一章讲两类「图的结构判定」问题，它们的共同点是： 算法都是一遍 BFS，难点全在「读题时相信了不该相信的话」。

主题	判定的是什么	等价条件	一遍 BFS 的产物
拓扑排序	有向图有没有环	无环 ⟺ 存在拓扑序	一个合法的拓扑序
二分图判定	无向图能不能两染色	二分图 ⟺ 无奇环	一组合法染色

而它们的下游用途更重要：拓扑序是 DAG 上 DP 的执行顺序（无后效性的来源）， 二分图染色是匹配、最小点覆盖、最大独立集的入口。

---

93.1　DAG 与拓扑序

DAG（Directed Acyclic Graph）：没有环的有向图。

拓扑序：把所有点排成一个线性序列，使得每条边 \(u \to v\) 都满足 \(u\) 排在 \(v\) 前面。

基本定理：

\[\text{有向图存在拓扑序} \iff \text{它是 DAG}\]

「⟸」的构造性证明就是 Kahn 算法本身：DAG 里必定存在入度为 0 的点 （否则从任意点一直往前走必然重复访问某点，形成环）， 取出它、删掉它的出边，剩下的图仍是 DAG，归纳即可。 「⟹」显然：环上的点谁都不能排在最前。

关于拓扑序的四个事实	说明
拓扑序一般不唯一	入度为 0 的点有多个时，先取哪个都行
拓扑序唯一 ⟺ 每一步都只有一个入度 0 点	等价于图上存在一条经过所有点的路径（哈密顿路）
拓扑序的逆序是反图的拓扑序	求「以某点为终点的最长路」时常用
拓扑序个数	计数是 #P-完全问题；\(n \le 20\) 时用状压 DP（103 章）

用途：

场景	怎么用
判有向图是否有环	拓扑排序能否排完全部 \(n\) 个点
课程 / 任务的先后依赖	拓扑序就是可行的执行顺序
DAG 上 DP	按拓扑序递推，天然满足无后效性（93.4）
关键路径（AOE 网）	拓扑序上正推最早开始、逆推最晚开始（117 章）
强连通分量缩点后的处理	缩点后必是 DAG（112 章）
判断差分约束是否有解	转化成负环检测（91 章）

---

93.2　Kahn 算法（入度法）

三步：

1. 统计所有点的入度，把入度为 0 的点全部入队；
2. 每次取出一个点 \(u\) 加入答案，把它所有出边 \(u \to v\) 的 \(v\) 的入度减 1， 减到 0 就入队；
3. 队列空时结束。若答案里的点数 \(< n\)，说明有环（环上的点入度永远减不到 0）。

S4 模板.docx 的拓扑排序模板（洛谷「旅行计划」）就是这个：

for(int i=1;i<=n;++i) if(!rd[i]) q.push(i);        // rd 是入度
while(!q.empty()){
    top[++cnt]=q.front();q.pop();
    for(int i=head[top[cnt]];i;i=bot[i].nx){
        rd[bot[i].nd]--;
        if(!rd[bot[i].nd]) q.push(bot[i].nd);
    }
}

模板

def topo_sort(n, start, adj, indeg):
    """Kahn 入度法拓扑排序（CSR 存图，点编号 1..n）。O(n + m)。

    返回 (order, is_dag)：order 是一个合法拓扑序；
    is_dag 为 False 说明图里有环（此时 order 是「环外部分」的拓扑序）。

    ★ 用列表当队列：order 既是结果也是队列，`for u in order` 一边遍历一边
      append。BFS / Kahn 从不真的删元素，所以这样是安全的，
      而且省掉了 deque.popleft() 的方法调用——n = 3e5 时能省掉 3e5 次调用。
    """
    deg = indeg[:]                           # 复制，不破坏调用方的入度数组
                                             # deg[v] 会被减到 0，是「还欠几个前驱」
    order = [v for v in range(1, n + 1) if deg[v] == 0]   # 无前驱的点先入队
    for u in order:                          # 列表在迭代中扩展是安全的
        # u 已确定排在最终序列里，于是它对每个后继的「约束」就此解除
        for i in range(start[u], start[u + 1]):
            v = adj[i]
            d = deg[v] - 1                   # 抵消掉 u -> v 这一条前驱约束
            deg[v] = d
            if d == 0:                       # 前驱全部就位 -> 可以出场了
                order.append(v)              # 归零的时刻就是入队的时刻，早一步都不行
    # 环上的点入度永远减不到 0，所以排不进 order；点数不足即说明有环
    return order, len(order) == n

for u in order: 这个写法是 Python 图论的一个小红利。 它成立的前提是「队列只在尾部追加、指针只往前走」——BFS、Kahn、 树上求 BFS 序都满足。但 0-1 BFS、SPFA 需要 appendleft 或重复入队， 就必须用 deque（见 33 章、91 章）。

判环：三种写法的对比

判环方式	复杂度	Python 评价
Kahn：排出的点数 \(< n\)	\(O(n+m)\)	✅ 首选，顺手得到拓扑序
DFS 三色标记（白/灰/黑），遇到灰点即有环	\(O(n+m)\)	⚠️ 必须写迭代 DFS，代码长
并查集	—	❌ 不能用：并查集判的是无向图的环

⚠️ 有向图的环不能用并查集判。并查集只知道「连通」， 不知道方向。\(1\to2\)、\(1\to3\) 在并查集里和 \(1\to2\)、\(2\to1\) 长得一样。 判有向环只有拓扑排序和 DFS 两条路。

自环与重边

情况	对 Kahn 的影响
自环 \(u \to u\)	\(u\) 的入度永远 \(\ge 1\)，自动被判为「有环」✅ 不用特判
重边 \(u \to v\) 两次	\(v\) 的入度加了 2，出边也遍历两次，减回 0 ✅ 自洽
孤立点（入度出度都 0）	一开始就入队 ✅

---

93.3　字典序最小的拓扑序

题目常问「若有多个拓扑序，输出字典序最小的那个」。

做法只有一处改动：把队列换成小根堆。 每一步在「当前所有入度为 0 的点」里取编号最小的。

from heapq import heapify, heappush, heappop


def topo_sort_lexmin(n, start, adj, indeg):
    """字典序最小的拓扑序。O((n + m) log n)。

    与 topo_sort 唯一的区别：队列 -> 小根堆。
    """
    deg = indeg[:]                           # deg[v] = v 还欠几个前驱
    h = [v for v in range(1, n + 1) if deg[v] == 0]
    heapify(h)                               # ★ O(n) 建堆，比逐个 heappush 快
    order = []                               # 结果和候选池必须分开：候选池要能重排
    ap = order.append                        # 绑定方法，省掉 n 次属性查找
    while h:
        u = heappop(h)                       # 在「当前所有可选点」里取编号最小的
        ap(u)
        for i in range(start[u], start[u + 1]):
            v = adj[i]
            d = deg[v] - 1
            deg[v] = d
            if d == 0:
                heappush(h, v)               # 新解锁的点丢进候选池，等下一轮竞争
    return order, len(order) == n            # 点数不足 = 有环

⚠️ 两个常见错法： 1. 先跑普通拓扑排序，再把结果排序 —— 排完就不是拓扑序了； 2. 把每个点的邻居表排序，然后用普通队列 —— 队列是 FIFO， 先入队的点可能编号更大，取出顺序仍然不是字典序最小。

贪心必须发生在「取出」的时刻，所以必须换成堆。

三种拓扑排序方式的对比

方式	复杂度	得到的序	Python 评价
Kahn + 列表/deque	\(O(n+m)\)	任意一个	✅ 默认；\(n=3\times10^5\) 轻松
Kahn + 小根堆	\(O((n+m)\log n)\)	字典序最小	✅ \(n \le 2\times10^5\) 可行
DFS 逆后序（退出时压栈，最后反转）	\(O(n+m)\)	任意一个	⚠️ 不用算入度，但 Python 必须写迭代 DFS

变体：

要求	做法
字典序最大	入堆时存 -v，取出时取负；或用最大堆技巧（35 章）
「让编号大的点尽量靠前」	⚠️ 不等于字典序最大！正解是在反图上求字典序最小，再整体反转
要求某些点必须相邻	一般无法用拓扑排序直接做，需要额外建图或状压

⚠️ 「编号大的尽量靠前」是个经典陷阱。 字典序最大是「第一位尽量大，其次第二位尽量大……」， 而「大的尽量靠前」是「\(n\) 的位置尽量靠前，然后 \(n-1\) 尽量靠前……」， 两者不同。后者要在反图上贪心「小的尽量靠后」，即反图求字典序最小后反转。

---

93.4　DAG 上的 DP

DAG 上 DP 之所以简单，是因为拓扑序直接给出了「无后效性」的执行顺序。

按拓扑序遍历，处理 \(u\) 时它的所有前驱都已算完，直接往后继推：

def dag_longest_path(n, start, adj, order):
    """DAG 上以每个点为终点的最长路（按点数计）。O(n + m)。

    对应 S4 模板里的「洛谷 旅行计划」：f[v] = 1 + max(f[u])，u 是 v 的前驱。
    order 由 topo_sort 给出。若要按边权计，把 1 换成 wt[i]。
    """
    f = [1] * (n + 1)                        # 每个点自己算 1 个
    for u in order:                          # ★ 按拓扑序推，前驱一定已经定好
        fu = f[u] + 1                        # 从 u 再走一条边到后继，长度 +1
        for i in range(start[u], start[u + 1]):
            v = adj[i]
            if fu > f[v]:
                f[v] = fu                    # 「往后推」而不是「回头找前驱」，省一次反图
    return f                                 # 处理到 u 时 f[u] 已终值，不会再被改


def dag_count_paths(n, start, adj, order, src, mod=1000000007):
    """从 src 出发到每个点的路径条数。O(n + m)。"""
    cnt = [0] * (n + 1)
    cnt[src] = 1                             # 起点自己算一条「空路径」
    for u in order:                          # 拓扑序保证 cnt[u] 在被读走时已经是终值
        c = cnt[u]
        if c:                                # 不可达的点不用往下推
            for i in range(start[u], start[u + 1]):
                cnt[adj[i]] = (cnt[adj[i]] + c) % mod   # 每次累加就取模，数值不膨胀
    return cnt

DAG 上能线性做的问题	说明
最长路 / 最短路	边权可以是负数，不需要 Dijkstra 也不需要 Bellman-Ford
路径计数	上面的 dag_count_paths
每个点能到达多少个点	逆拓扑序 + bitset（Python 用大整数当位集，见 46 章）
最小路径覆盖	$n - $ 二分图最大匹配（93.6）
关键路径（AOE 网）	正推 ve、逆推 vl，ve == vl 的活动即关键活动

DAG 最短路允许负权，这是它和一般图最重要的区别。 Dijkstra 要求非负权，Bellman-Ford 要 \(O(nm)\)； 而 DAG 上按拓扑序一遍递推就是 \(O(n+m)\)，负权照做。 「无环」这个条件的价值就在这里。见 91-最短路。

关键路径（AOE 网、工程最早/最晚完工时间）是 DAG 最长路的直接应用， 完整讲解在 117-图论进阶：k短路与关键路径。

---

93.5　二分图判定

定义与核心定理

二分图：点集能划分成两个独立集 \(X, Y\)（集合内部没有边）， 使每条边都连接 \(X\) 中的一点和 \(Y\) 中的一点。

\[\textbf{二分图} \iff \textbf{不存在奇环}\]

证明思路：

• ⟹：若是二分图，沿着环走每一步都在两侧之间跳， 回到起点必须跳偶数次，所以所有环长为偶数；
• ⟸：若无奇环，就按「到起点的距离的奇偶性」染色。 若某条边两端同色，说明它们到起点的距离奇偶相同， 这条边加上两条路径构成一个奇环，矛盾。

推论：树一定是二分图（无环），偶环是二分图，三角形不是。

做法一：BFS 染色

def is_bipartite_bfs(n, start, adj):
    """BFS 染色判二分图（CSR 存图）。返回 (是否二分图, color)。

    color[v]：0 = 未染，1 / 2 = 两侧。用 bytearray 存，比 list 省 8 倍内存。

    ★ 必须对每个未染色点各起一轮 —— 图不保证连通。
    """
    color = bytearray(n + 1)                 # 全 0 起步：所有点都还没染
    for root in range(1, n + 1):
        if color[root]:
            continue                         # 已被前面某个连通块染过了
        color[root] = 1                      # 新连通块的起点随便定一侧，不影响判定
        q = [root]                           # 列表当队列，边遍历边 append
        for u in q:
            cu = color[u]
            nc = 3 - cu                      # 1 <-> 2 的对换
            for i in range(start[u], start[u + 1]):
                v = adj[i]
                cv = color[v]
                if cv == 0:
                    color[v] = nc            # 边的两端必须异色，直接染成对侧
                    q.append(v)
                elif cv == cu:               # 同色边 -> 存在奇环
                    return False, color      # 一条矛盾边就足以否定整张图
    return True, color                       # 全图染完没冲突 = 是二分图

为什么用 BFS 而不是 DFS：判定逻辑对遍历顺序完全不敏感， 而 Python 里递归 DFS 在 \(n \ge 10^4\) 的链上必爆栈。 BISHI100 的题目标题写的是「染色判定：DFS」，但用 BFS 得到的答案一模一样， 而且不用改写成迭代——题面的算法名不是约束。见 90.5。

做法二：扩展域并查集

把每个点 \(x\) 拆成两个域：\(x\)（在左侧）与 \(x+n\)（在右侧）。 每条边 \((u,v)\) 表达的是「\(u\) 与 \(v\) 异侧」：

\[\texttt{union}(u,\ v+n),\qquad \texttt{union}(u+n,\ v)\]

若在处理某条边之前 \(u\) 与 \(v\) 已经同域，说明前面的边已经推出「\(u,v\) 同侧」， 和这条边冲突 ⟹ 存在奇环。

def is_bipartite_dsu(n, edges):
    """扩展域并查集判二分图。edges 是 (u, v) 列表，点编号 1..n。O(m α(n))。

    x     表示「x 在左侧」这个命题
    x + n 表示「x 在右侧」这个命题
    一条边 (u, v) 断言两点异侧，于是把 u 与 v 的对侧域合并。
    """
    parent = list(range(2 * n + 2))          # 开两倍：下标 1..n 是左域，n+1..2n 是右域

    def find(x):
        """迭代路径压缩。递归版在 3e5 的退化链上必爆 C 栈。"""
        r = x
        while parent[r] != r:                # 一路向上找根
            r = parent[r]
        while parent[x] != r:                # 把沿途的点直接挂到根下
            parent[x], x = r, parent[x]
        return r

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                         # 已被推出「同侧」，与本边冲突
            return False                     # 必须在合并之前判，合并后就查不出来了
        parent[ru] = find(v + n)             # u 的左域 == v 的右域
        parent[rv] = find(u + n)             # 对称地再断言一次，两个域才同步
    return True                              # 所有边都能自洽 = 无奇环 = 二分图

扩展域并查集的通用讨论见 38.6。

两种做法怎么选

	BFS 染色	扩展域并查集
复杂度	\(O(n+m)\)	\(O(m\,\alpha(n))\)，近似线性
需要建邻接表	✅ 必须	❌ 只要边表（省掉 CSR 的建表时间与内存）
能顺便输出具体染色	✅ color 数组	⚠️ 要再走一遍：find(x) == find(1) 判同侧
支持边一条条加入 / 在线判定	❌ 每次都要重跑	✅ 天然在线
支持删边	❌	❌（并查集不能拆）
常数（Python）	小	更小（不用建邻接表）
代码量	中	中

决策： - 一次性判定 + 需要输出染色方案 → BFS 染色（BISHI100）； - 边是逐条给出的、要求每加一条就判一次 → 扩展域并查集； - \(n,m\) 很大且只要 YES/NO → 扩展域并查集（省掉建邻接表的 \(O(n+m)\) 内存）。

三个高频陷阱

⚠️ 陷阱一：「保证连通」不可信。 BISHI100 的题面明写「保证连通」，但样例 2 实际上是不连通的 （三角形 \(1\)–\(2\)–\(3\) 加上孤立的边 \(4\)–\(5\)）。 只从 1 号点搜一次就收工，会漏掉别的连通块里的奇环。 无论题面怎么说，永远对每个未访问点起一轮。

⚠️ 陷阱二：颜色的编码。 用 0 表示「未染色」、1 / 2 表示两侧，这样 color 一个数组同时充当 访问标记和颜色（和 BFS 里 dist = -1 兼任标记是同一个手法，见 90.4）。 别用 0/1 表示两种颜色——那样必须再开一个 vis 数组，多一半内存和一次判断。 对换用 nc = 3 - cu（\(1 \leftrightarrow 2\)），比 1 if cu == 2 else 2 快也短。

自环（若题目允许）会让图不是二分图（长度 1 的奇环）： 染色法里 \(v = u\) 时 cv == cu 成立，并查集法里 find(u) == find(v) 恒成立， 两种做法都自动判死，不用特判。BISHI100 保证无自环。

⚠️ 陷阱三：重边无影响，不必去重。 重边 \((u,v)\) 两次只是把同一条约束重复断言一次，两种做法都自洽。 花时间去重是纯浪费（\(3\times10^5\) 条边建 set 要 0.3 秒以上）。

---

93.6　二分图匹配简介

概念

术语	含义
匹配	一组边，其中任意两条边不共享端点
最大匹配	边数最多的匹配
完美匹配	覆盖了所有点的匹配（要求两侧点数相等）
增广路	一条起点终点都是未匹配点、且边「非匹配-匹配-非匹配…」交替的路径
增广定理	一个匹配是最大匹配 ⟺ 不存在增广路

增广路为什么有用：沿着一条增广路把所有边的「匹配/非匹配」状态取反， 匹配数恰好 \(+1\)（非匹配边比匹配边多一条）。

匈牙利算法

思想：对左部每个点依次尝试「找一条增广路」。 从 \(u\) 出发枚举它的邻居 \(v\)：若 \(v\) 未匹配，直接配上； 若 \(v\) 已被 \(w\) 占着，就递归让 \(w\) 去另找一个，让位成功则 \(u\) 占 \(v\)。

import sys


def hungarian(n_left, n_right, adj):
    """匈牙利算法求二分图最大匹配。左部 1..n_left，右部 1..n_right。

    adj[u] 是左部点 u 的右部邻居列表。
    返回 (最大匹配数, match_right)；match_right[v] = 与 v 匹配的左部点，0 = 未匹配。
    复杂度 O(V * E)。

    ⚠️ 递归深度可达 n_left，Python 下 n_left >= 900 就要调 setrecursionlimit，
       n_left >= 1e4 则必须改写成迭代（或者干脆放弃这个算法）。
    """
    sys.setrecursionlimit(max(3000, n_left * 2 + 100))   # 递归深度上界就是左部点数
    match_right = [0] * (n_right + 1)            # 只需记右部的归属，左部由它反推

    def try_augment(u, vis):
        """尝试为 u 找一条增广路。vis 保证本轮每个右部点只被尝试一次。"""
        for v in adj[u]:
            if vis[v]:
                continue                         # 本轮已经试过 v，再试必然死循环
            vis[v] = 1
            w = match_right[v]                   # 目前占着 v 的左部点，0 = 空位
            if w == 0 or try_augment(w, vis):    # v 空着，或占着的人能挪走
                match_right[v] = u               # 抢下 v；沿途每层都会做同样的改写
                return True                      # 这正是「沿增广路取反」的效果
        return False                             # 邻居全试遍也挪不动 -> 本轮放弃 u

    res = 0
    for u in range(1, n_left + 1):               # 左部点逐个尝试，成功一次匹配数 +1
        vis = bytearray(n_right + 1)             # ★ 每轮重置
        if try_augment(u, vis):                  # 提到循环外会漏解，去掉会死循环
            res += 1
    return res, match_right

⚠️ vis 必须每轮重置，且「每个右部点本轮只尝试一次」。 少了 vis 会死循环（\(u\) 让 \(w\) 挪，\(w\) 又来抢 \(u\) 刚放弃的位置）； 把 vis 提到循环外则会漏解。这是匈牙利算法唯一的实现难点。

相关定理（考点密集区）

对二分图，设最大匹配为 \(M\)，点数为 \(n\)：

定理	结论
König 定理	最小点覆盖 \(= M\)
最大独立集	\(= n - M\)
最小边覆盖（无孤立点）	\(= n - M\)
DAG 的最小路径覆盖	\(= n - M\)（拆点建二分图：每个点拆成「出点」和「入点」）
最大权匹配	KM 算法 / 费用流（超纲，见网络流）

「最小点覆盖 = 最大匹配」是 König 定理，只对二分图成立。 一般图的最小点覆盖是 NP-难的。看到「选最少的点覆盖所有边」+「图是二分的」， 就是这个定理。

Python 下的可行规模

匈牙利算法的主循环是 \(O(V \cdot E)\) 次纯 Python 层操作：

规模	Python 层操作量	现实性
\(V = 200\)，\(E = 5000\)	\(10^6\)	✅ 约 0.5 s
\(V = 500\)，\(E = 5000\)	\(2.5\times10^6\)	⚠️ 1–2 s，勉强
\(V = 1000\)，\(E = 10^4\)	\(10^7\)	❌ 5–10 s
\(V = 10^4\)，\(E = 10^5\)	\(10^9\)	❌ 完全不可能

判据：Python 下匈牙利算法的现实上界是 \(V \cdot E \le 2\times10^6\)， 也就是「左部点几百个、边几千条」的规模。 稠密二分图要用 Hopcroft-Karp（\(O(E\sqrt V)\)，BFS 分层 + 多路增广）， 但它的 Python 常数依然很大，\(E \le 10^5\) 是上限。

好消息：笔试题单里没有真正的二分图匹配题—— BISHI100 只判二分图，BISHI38 是构造题。匹配在这里只需要知道概念和定理， 因为「最小点覆盖 / 最大独立集 / 最小路径覆盖」经常作为结论出现在其它题里。

---

93.7　例题

BISHI100 【模板】二分图结构Ⅰ-A ‖ 染色判定（中等）

给定 \(n\) 个顶点、\(m\) 条边的无向图（\(1 \le n, m \le 3\times10^5\)）， 判定它是否为二分图。有重边、无自环、题面声称保证连通。 是则输出 YES，否则 NO。 时限：C/C++ 5 秒，其他语言 10 秒；空间：其他语言 2048 MB。 题面见 BISHI100 原题（牛客）。 题解见 solutions/BISHI100.py（已通过官方样例验证）。

\(n, m \le 3\times10^5\)，是 90.2 选型表里明确要求 用 CSR 存图的规模。判定用 BFS 染色。

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    us = [int(x) for x in data[2::2][:m]]    # ★ 切片 + 推导，比循环里两次索引快
    vs = [int(x) for x in data[3::2][:m]]    # 边是 u1 v1 u2 v2... 交替排列的

    # ---- CSR 邻接表：度数 -> 前缀和 -> 填充，全程无 append 扩容 ----
    deg = [0] * (n + 2)                      # 第一趟：数度数
    for x in us:
        deg[x] += 1
    for x in vs:
        deg[x] += 1                          # 无向图，一条边给两端各加 1 度
    start = [0] * (n + 2)                    # 第二趟：前缀和 -> 每个点的起始下标
    s = 0
    for i in range(1, n + 1):
        start[i] = s                         # s = 1..i-1 的度数之和
        s += deg[i]
    start[n + 1] = s                         # 哨兵；由握手定理，s 恰好等于 2m
    pos = start[:]                           # 填充游标
    adj = [0] * s                            # 第三趟：一次开够，按游标回填
    for i in range(m):
        a = us[i]; b = vs[i]
        adj[pos[a]] = b; pos[a] += 1         # 写进 a 的下一个空位后游标右移
        adj[pos[b]] = a; pos[b] += 1         # 反方向同理

    color = bytearray(n + 1)                 # 0 = 未染色，1 / 2 = 两种颜色
    q = deque()
    for root in range(1, n + 1):             # ★ 题面说「保证连通」但样例 2 不连通
        if color[root]:
            continue                         # 已属于前面染过的连通块
        color[root] = 1                      # 新块的起点随便定一侧
        q.append(root)
        while q:
            u = q.popleft()                  # list.pop(0) 是 O(n)，这里必须 deque
            cu = color[u]
            nc = 3 - cu                      # 1 <-> 2
            for i in range(start[u], start[u + 1]):
                v = adj[i]
                cv = color[v]
                if cv == 0:
                    color[v] = nc            # 边的两端必须异色
                    q.append(v)
                elif cv == cu:               # 同色边 -> 存在奇环
                    sys.stdout.write("NO\n")
                    return                   # 找到一处矛盾即可收工
    sys.stdout.write("YES\n")                # 全图染完无冲突


main()

复杂度 \(O(n+m)\)。主循环是 \(2m = 6\times10^5\) 次内层迭代， 加上建 CSR 的 \(\sim10^6\) 次，本机实测 1.5–2 秒，10 秒时限很宽裕。

五个坑：

1. 「保证连通」是假的——这是本题最大的坑。 样例 2 是「三角形 \(1\)–\(2\)–\(3\)」加上「孤立边 \(4\)–\(5\)」， \(n=5,m=4\)，明显不连通。必须对每个未染色点起一轮， 否则若奇环恰好落在第二个连通块里就会漏判。 更普适的教训写在 90.8 的速查里： 题面的「保证」永远要用样例交叉验证；
2. 必须 BFS，不能递归 DFS。\(3\times10^5\) 个点的链会让递归深度达到 \(3\times10^5\)， RecursionError 是好结果，调大上限后是无提示的段错误；
3. 队列必须 deque。list.pop(0) 是 \(O(n)\)， \(3\times10^5\) 个点会退化成 \(9\times10^{10}\) 次操作（33 章）；
4. 邻接表必须 CSR。\(3\times10^5\) 个 list 对象仅对象头就 17 MB 以上， 加上元素开销会很吃紧；defaultdict(list) 更慢（90.2）；
5. 有重边，但完全不影响染色判定，不要浪费时间去重。

data[2::2][:m] 这个写法值得单独说。 边数据是 u1 v1 u2 v2 ... 交替排列的，用步长切片一次取出所有 \(u\)、 再一次取出所有 \(v\)，两次操作都在 C 层完成； 换成 for i in range(m): u = int(data[2+2*i]); ... 要做 \(m\) 次下标计算 + 两次索引。 \(m = 3\times10^5\) 时这个差别是零点几秒。[:m] 是防止末尾多余 token 混进来。

也可以用扁平域并查集：不建邻接表，直接扫 \(m\) 条边做 union(u, v+n) / union(u+n, v)（93.5 做法二）。 内存更省（省掉 \(6\times10^5\) 长的 adj），代码也更短。 本题两种都能过，推荐先掌握染色版——因为它能输出具体的划分方案， 而很多题会追问「请给出一种划分」。

BISHI38 有向二分图构造（简单，本章视角）

\(N \le 10^5\) 点、\(M \le 2\times10^5\) 边的有向图（可能有重边）， 给每个点染黑或白。起点黑、终点白的边称为核心边。 要求构造一种染色使核心边数 \(\ge \lfloor M/4 \rfloor + 1\)，并输出所有核心边的编号。 题面见 BISHI38 原题（牛客）。 题解见 solutions/BISHI38.py（已通过官方样例验证）。

这题挂在本章是一个「名不副实」的例子，值得专门辨析。

它的标题里有	但它其实
「二分图」	不是二分图判定：它不要求「同色之间无边」，同色边只是不计分
「构造」	是真的构造：要输出一个具体方案
两染色	染色的目标是最大化跨色边数，而不是消灭同色边

关键区别：二分图判定要求所有边跨色（做不到就 NO）， 本题只要求至少 \(\lfloor M/4\rfloor+1\) 条边「黑 → 白」—— 这是个最大割（Max-Cut）风味的优化问题，而最大割是 NP-难的。 所以本题给了一个很松的阈值 \(M/4\)，好让局部搜索能过。

第一步：阈值为什么一定达得到（概率法）。 每个点独立等概率染黑/白，每条边成为核心边的概率是 \(\frac12\times\frac12=\frac14\)，故 \(\mathbb{E}[\text{核心边数}] = M/4\)。核心边数是整数， 而「全染黑」这种方案给出 \(0 < M/4\)（\(M \ge 1\)），说明它不是常数， 于是必然存在某种染色严格大于 \(M/4\)，而「整数 \(> M/4\)」正是「\(\ge \lfloor M/4\rfloor+1\)」。

第二步：局部搜索（爬山）把它构造出来。 记 \(\mathrm{outW}(v)\) = \(v\) 指向白点的出边数，\(\mathrm{inB}(v)\) = 黑点指向 \(v\) 的入边数。 因为无自环，翻转 \(v\) 的颜色只影响与 \(v\) 相邻的边：

\(v\) 当前颜色	翻转后核心边数的增量
黑 → 白	\(\mathrm{inB}(v) - \mathrm{outW}(v)\)
白 → 黑	\(\mathrm{outW}(v) - \mathrm{inB}(v)\)

# [片段] 爬山主循环：只要某点翻转能严格增加答案就翻
dq = deque(range(1, n + 1))                  # 待检查队列
inq = bytearray([1]) * (n + 1)               # 初始所有点都待检查
while dq:
    v = dq.popleft()
    inq[v] = 0                               # 出队，之后邻居变化时可以重新入队
    # 无自环，所以翻 v 的收益只由它自己的邻边决定，可以 O(1) 算出
    delta = (inB[v] - outW[v]) if color[v] else (outW[v] - inB[v])
    if delta <= 0:
        continue                             # 翻了不划算，跳过
    core += delta                            # 严格增加，所以循环一定终止
    color[v] ^= 1                            # 异或 1 = 黑白对换
    # 翻转 v 只影响它的邻居：更新它们的 outW / inB，并重新入队
    ...

每次翻转答案至少 \(+1\)、上界是 \(M\)，所以一定终止。

第三步：整体取反这一招不能少。 单点翻转对「所有边都是白→黑」这种局面 无能为力（每个点单独翻都不划算），而整体取反一步就翻盘 （取反后的核心边数 = 原来的「白→黑」边数）。

这题在本章的意义：

看到「二分图」三个字，第一件事是判断题目要的是 「所有边跨色」（判定，多项式可解）还是「尽量多边跨色」（最大割，NP-难）。 前者一遍 BFS，后者只能靠阈值宽松 + 局部搜索。 两者的算法完全没有共同点，混淆了就会去写染色 BFS 然后输出 NO。

构造方法论（概率法证存在 + 爬山找解 + 固定随机种子）的完整讲解在 48-构造，完整代码见 solutions/BISHI38.py。

本章需要记住的两个 Python 要点：

1. 爬山队列用 deque + inq 去重标记。不做去重标记， 同一个点会被反复入队，队列长度膨胀到 \(O(M)\)；
2. 有重边，所有统计必须按「边」而不是「点对」来算， 邻接表里要保留重复项——outW/inB 是计数，不是集合大小。

---

93.8　本章速查

拓扑排序

要点	结论
拓扑序定义	每条边 \(u\to v\) 都满足 \(u\) 排在 \(v\) 前
存在性	存在拓扑序 ⟺ 是 DAG
唯一性	每一步只有一个入度 0 点 ⟺ 存在哈密顿路
Kahn 三步	入度 0 入队 → 取出并把后继入度 \(-1\) → 减到 0 入队
判环	排出的点数 \(< n\)
❌ 并查集判有向环	不行，它不知道方向
自环	入度永远 \(\ge1\)，自动被判有环，不用特判
重边	入度加 2、出边遍历 2 次，自洽
队列容器	列表当队列 + for u in order（Kahn 只在尾部追加）
什么时候必须 deque	0-1 BFS、SPFA（需要 appendleft / 重复入队）
字典序最小拓扑序	队列换小根堆，\(O((n+m)\log n)\)
❌ 先拓扑再排序	排完就不是拓扑序了
❌ 邻居表排序 + 普通队列	队列是 FIFO，取出顺序仍不对
「编号大的尽量靠前」	⚠️ 不是字典序最大；反图求字典序最小再反转
DAG 上 DP	按拓扑序递推，天然无后效性
DAG 最短路	允许负权，\(O(n+m)\)，不用 Dijkstra
关键路径	拓扑序正推 ve + 逆推 vl（117 章）

二分图

要点	结论
定义	点集可分为两个独立集，所有边跨集合
核心定理	二分图 ⟺ 无奇环
树	一定是二分图
做法一	BFS 染色（color 用 bytearray，nc = 3 - cu）
做法二	扩展域并查集：union(u, v+n) / union(u+n, v)，冲突即 find(u)==find(v)
只要 YES/NO + 边逐条给出	选并查集（在线、不用建邻接表）
要输出具体划分	选 BFS 染色
⚠️ 「保证连通」	不可信（BISHI100 样例 2 就不连通），对每个点起一轮
⚠️ 颜色编码	0 = 未染色，1/2 = 两侧；nc = 3 - cu。别用 0/1 当两色
自环	长度 1 的奇环，两种做法都自动判死，不用特判
⚠️ 重边	无影响，不要去重（去重比判定还慢）
递归 DFS	❌ \(n \ge 10^4\) 必爆栈，一律 BFS 或迭代
最大匹配	匈牙利：为左部每点找增广路；vis 每轮重置
König 定理	最小点覆盖 \(=\) 最大匹配（只对二分图）
最大独立集	$n - $ 最大匹配
DAG 最小路径覆盖	$n - $ 最大匹配（拆点建二分图）
⚠️ 「尽量多边跨色」	是最大割（NP-难），不是二分图判定（BISHI38）

规模	Python 现实性
Kahn，\(n,m \le 3\times10^5\)（CSR）	✅ 约 1.5–2 s
Kahn + 堆，\(n \le 2\times10^5\)	✅ 堆操作 \(2\times10^5\) 次
BFS 染色，\(n,m \le 3\times10^5\)	✅ 约 1.5–2 s（BISHI100）
扩展域并查集，\(m \le 3\times10^5\)	✅ 更省内存（不建邻接表）
DAG 上 DP，\(n,m \le 3\times10^5\)	✅ 与拓扑排序同阶
匈牙利，\(V\cdot E \le 2\times10^6\)	⚠️ 上限（\(V\) 几百、\(E\) 几千）
匈牙利，\(V=10^3\)、\(E=10^4\)	❌ \(10^7\) 次 Python 层递归调用
Hopcroft-Karp，\(E \le 10^5\)	⚠️ 理论 \(O(E\sqrt V)\)，Python 常数仍很大

看到什么 → 想到什么
「课程/任务的依赖顺序」
「判有向图是否有环」
「输出字典序最小的顺序」
「DAG 上求最长/最短路、路径数」
「工程最早完工时间 / 关键活动」
「能否分成两组使组内无冲突」
「是否存在奇环」
「敌人的敌人是朋友」+ 只有两派
「选最少的点覆盖所有边」+ 二分图
「最多选多少个互不相邻的点」+ 二分图
「让尽量多的边跨越两色」