差分约束系统 (System of Difference Constraints)

差分约束系统（System of Difference Constraints） 是一种将多元一次不等式组转化为图论最短路/最长路求解的经典建模算法。

在算法竞赛与系统设计中，许多涉及相对时序安排、区间点覆盖、流水线调度及偏序关系排布的问题，本质上都可以转化为差分约束系统。

---

1. 核心理论与图论同构

1.1 什么是差分约束系统？

一个差分约束系统由 \(n\) 个变量 \(x_1, x_2, \dots, x_n\) 以及 \(m\) 个二元一次不等式组成。每个不等式具有如下标准形式：

\[ x_i - x_j \le c_k \]

其中 \(c_k\) 为常数。

我们的目标是： 1. 判定可行性：判断是否存在一组实数（或整数）赋值 \((x_1, x_2, \dots, x_n)\) 满足所有 \(m\) 个不等式约束； 2. 求解特定极值：在满足所有约束的前提下，求解某个变量的最大值、最小值，或两变量间差值的极值（如 \(\max(x_n - x_1)\)）。

---

1.2 三角不等式与图论映射

在赋权有向图的最短路径问题中，对于任意一条从顶点 \(u\) 指向顶点 \(v\)、权值为 \(w(u, v)\) 的有向边，单源最短路距离 \(dist\) 必须满足三角不等式（Triangle Inequality）：

\[ dist[v] \le dist[u] + w(u, v) \iff dist[v] - dist[u] \le w(u, v) \]

对比差分约束的不等式形式：

\[ x_i - x_j \le c_k \iff x_i \le x_j + c_k \]

两者的数学结构完全一一对应：

flowchart LR
    subgraph Math["代数不等式"]
        E1["x_i - x_j <= c_k"] --> E2["x_i <= x_j + c_k"]
    end
    subgraph Graph["图论有向边"]
        Vj["顶点 j (变量 x_j)"] -->|"边权 c_k"| Vi["顶点 i (变量 x_i)"]
    end
    Math <==>|"1:1 同构映射"| Graph

• 变量 \(\to\) 顶点：系统中的每一个变量 \(x_k\) 对应图中的一个顶点 \(k\)；
• 不等式 \(\to\) 有向边：不等式 \(x_i - x_j \le c\) 对应一条从 \(j\) 指向 \(i\)、边权为 \(c\) 的有向边（\(j \xrightarrow{c} i\)）；
• 常数 \(c\) \(\to\) 边权：\(c\) 可以是正数、负数或零。

---

1.2.1 极简入门案例：手把手建图与求解全流程

为了彻底掌握差分约束的计算过程，我们通过一个包含 3 个变量、5 个不等式的极简实例，完整演示建图、松弛求解与结果验证的全过程。

1. 问题设定

给定关于变量 \(x_1, x_2, x_3\) 的 5 个不等式约束：

\[ x_1 - x_2 \le 5 \]

\[ x_2 - x_1 \le -2 \]

\[ x_2 - x_3 \le 3 \]

\[ x_3 - x_1 \le 4 \]

\[ x_3 - x_2 \le 1 \]

求解目标：设基准点 \(x_1 = 0\)，求出一组满足所有约束的可行解，使得各变量的值达到最大值。

---

2. 第一步：将不等式转化为有向边（建图）

根据转化规则 \(x_i - x_j \le c \iff x_i \le x_j + c \implies j \xrightarrow{c} i\)：

1. \(x_1 - x_2 \le 5 \implies\) 建立有向边 \(2 \xrightarrow{5} 1\)
2. \(x_2 - x_1 \le -2 \implies\) 建立有向边 \(1 \xrightarrow{-2} 2\)
3. \(x_2 - x_3 \le 3 \implies\) 建立有向边 \(3 \xrightarrow{3} 2\)
4. \(x_3 - x_1 \le 4 \implies\) 建立有向边 \(1 \xrightarrow{4} 3\)
5. \(x_3 - x_2 \le 1 \implies\) 建立有向边 \(2 \xrightarrow{1} 3\)

建立的有向图拓扑结构如下：

flowchart LR
    V1((x_1)) -->|"-2"| V2((x_2))
    V2 -->|"5"| V1
    V1 -->|"4"| V3((x_3))
    V2 -->|"1"| V3
    V3 -->|"3"| V2

---

3. 第二步：以起点 x_1 = 0 运行最短路松弛

我们以节点 \(1\) 为源点，执行单源最短路算法（松弛操作：\(dist[v] = \min(dist[v], dist[u] + w)\)）：

• 初始状态： \(dist = [dist[1]=0, dist[2]=+\infty, dist[3]=+\infty]\)
• 第 1 轮松弛（考察从节点 1 出发的出边）：
• 边 \(1 \xrightarrow{-2} 2\)：\(dist[2] = \min(+\infty, dist[1] - 2) = \min(+\infty, 0 - 2) = -2\)
• 边 \(1 \xrightarrow{4} 3\)：\(dist[3] = \min(+\infty, dist[1] + 4) = \min(+\infty, 0 + 4) = 4\)
• 当前状态更新为：\([0, -2, 4]\)
• 第 2 轮松弛（考察从节点 2 出发的出边）：
• 边 \(2 \xrightarrow{5} 1\)：\(dist[1] = \min(0, dist[2] + 5) = \min(0, -2 + 5) = 0\)（无需更新）
• 边 \(2 \xrightarrow{1} 3\)：\(dist[3] = \min(4, dist[2] + 1) = \min(4, -2 + 1) = -1\)（成功松弛！从 4 缩紧为 -1）
• 当前状态更新为：\([0, -2, -1]\)
• 第 3 轮松弛（考察从节点 3 出发的出边）：
• 边 \(3 \xrightarrow{3} 2\)：\(dist[2] = \min(-2, dist[3] + 3) = \min(-2, -1 + 3) = -2\)（无需更新）
• 算法收敛：所有边均已无法继续松弛，算法终止！

最终求得的最短路结果为：

\[ (x_1, x_2, x_3) = (0, -2, -1) \]

---

4. 第三步：代入原不等式组验证

将所得结果 \((x_1 = 0, x_2 = -2, x_3 = -1)\) 代入原系统的 5 个不等式逐一核验：

原始不等式	代入数值计算	结果判定	约束状态
\(x_1 - x_2 \le 5\)	\(0 - (-2) = 2 \le 5\)	成立	松弛裕量为 3
\(x_2 - x_1 \le -2\)	\(-2 - 0 = -2 \le -2\)	成立	紧约束（等号严格成立）
\(x_2 - x_3 \le 3\)	\(-2 - (-1) = -1 \le 3\)	成立	松弛裕量为 4
\(x_3 - x_1 \le 4\)	\(-1 - 0 = -1 \le 4\)	成立	松弛裕量为 5
\(x_3 - x_2 \le 1\)	\(-1 - (-2) = 1 \le 1\)	成立	紧约束（等号严格成立）

所有 5 个不等式均被完美满足，解完全合法！

---

5. 深入观察：为什么这是在 x_1 = 0 下的「最大值」？

我们尝试把 \(x_2\) 或 \(x_3\) 的值略微调大一点点： * 若尝试令 \(x_2 = -1\)（比 \(-2\) 更大）： 不等式 2 要求 \(x_2 - x_1 \le -2 \implies -1 - 0 = -1 \le -2\)，立即产生矛盾！ * 若尝试令 \(x_3 = 0\)（比 \(-1\) 更大）： 不等式 5 要求 \(x_3 - x_2 \le 1 \implies 0 - (-2) = 2 \le 1\)，立即产生矛盾！

这表明：\((0, -2, -1)\) 是在基准点 \(x_1 = 0\) 约束下，其他变量所能被允许取到的最大上限（Upper Bound）。

---

6. 负权环导致无解的情形（反例演示）

假设在原系统中追加第 6 个不等式：

\[ x_1 - x_2 \le -3 \]

• 该不等式要求建边 \(2 \xrightarrow{-3} 1\)；
• 此时图中在顶点 1 和顶点 2 之间形成了环路：\(1 \xrightarrow{-2} 2 \xrightarrow{-3} 1\)；
• 环路的总边权为：\((-2) + (-3) = -5 < 0\)，构成了一个负权环！
• 将两个对应不等式相加：\((x_2 - x_1) + (x_1 - x_2) \le (-2) + (-3) \iff 0 \le -5\)。
• 出现了 \(0 \le -5\) 这一永远无法成立的荒谬结论，数学上产生自相矛盾。SPFA 算法在检测到负环后立即判定系统无解！

---

1.3 对偶模型：最短路（求上界） vs 最长路（求下界）

差分约束系统具有高度对称的对偶性，取决于题目求的是变量的最大值（上界）还是最小值（下界）：

flowchart TD
    A["差分约束问题"] --> B["求最大值 / 上界"]
    A --> C["求最小值 / 下界"]
    B --> B1["统一化为: x_i - x_j <= c"]
    B1 --> B2["建边: j -> i (权值 c)"]
    B2 --> B3["运行【最短路】算法 (SPFA)"]
    B3 --> B4["负权环 => 系统无解 (自相矛盾)"]
    C --> C1["统一化为: x_i - x_j >= c"]
    C1 --> C2["建边: j -> i (权值 c)"]
    C2 --> C3["运行【最长路】算法 (SPFA)"]
    C3 --> C4["正权环 => 系统无解 (无限增大)"]

模型一：小于等于号 (<=) -> 最短路 -> 求解最大值（上界）

• 建边准则：将所有约束化为 \(x_i \le x_j + c\)，建立有向边 \(j \xrightarrow{c} i\)；
• 算法选择：以超级源点出发跑单源最短路（SPFA / Bellman-Ford）；
• 无解判据：图中存在负权环。
• 证明：设负环上有 \(k\) 个顶点 \(v_1, v_2, \dots, v_k\)，累加环上不等式： \((x_{v_2} - x_{v_1}) + (x_{v_3} - x_{v_2}) + \dots + (x_{v_1} - x_{v_k}) \le \sum w < 0 \implies 0 \le \sum w < 0\)，产生逻辑矛盾！
• 最优解意义：若无负环，求出的 \(dist[i]\) 即为满足 \(x_0 = 0\) 时变量 \(x_i\) 能取得的最大可行值。

模型二：大于等于号 (>=) -> 最长路 -> 求解最小值（下界）

• 建边准则：将所有约束化为 \(x_i \ge x_j + c\)，建立有向边 \(j \xrightarrow{c} i\)；
• 算法选择：以超级源点出发跑单源最长路（SPFA）（松弛条件为 \(dist[v] < dist[u] + w\)）；
• 无解判据：图中存在正权环。
• 最优解意义：若无正环，求出的 \(dist[i]\) 即为满足 \(x_0 = 0\) 时变量 \(x_i\) 必须满足的最小可行值。

---

1.3.1 深度思辨：为什么最短路求解的是最大值？

很多初学者在初次接触差分约束时都会产生一个强烈的反直觉困惑：

“明明跑的是【最短路】，为什么求出来的变量值反而是【最大值】？”

1. 生活直觉：多重天花板的“最低限度”

假设有三条独立规则同时限制变量 \(x\) 的取值上限（以基准点 \(x_0 = 0\) 为参考）： * 规则 1：\(x \le 100\) * 规则 2：\(x \le 80\) * 规则 3：\(x \le 120\)

如果这三条规则必须同时满足，\(x\) 最大能取到多少？ 显然是：

\[ x = \min(100, 80, 120) = 80 \]

• 若取 \(x = 81\)，虽然满足规则 1 和规则 3，但直接违反了规则 2；
• 只有取所有上限中的最小值（最低的天花板），才能在不违反任何一条约束的前提下，让 \(x\) 达到最大可能的可行值。

在差分约束中：从源点到终点的每一条路径，都给出了一条连锁上限约束；而最短路，正是所有连锁上限中最紧迫的那一个“天花板”！

2. 代数证明：不等式链的裂项相消

设虚拟源点为 \(x_0 = 0\)。假设从源点 \(0\) 到变量 \(x_i\) 存在一条包含 \(k\) 条边的路径 \(P\)：

\[ 0 \xrightarrow{w_1} v_1 \xrightarrow{w_2} v_2 \xrightarrow{w_3} \dots \xrightarrow{w_k} i \]

根据建边规则（\(j \xrightarrow{c} i \iff x_i - x_j \le c\)），路径上的每一条边都对应一个不等式：

\[ x_{v_1} - x_0 \le w_1 \]

\[ x_{v_2} - x_{v_1} \le w_2 \]

\[ x_i - x_{v_{k-1}} \le w_k \]

将整条路径上的所有不等式相加：

\[ (x_{v_1} - x_0) + (x_{v_2} - x_{v_1}) + \dots + (x_i - x_{v_{k-1}}) \le w_1 + w_2 + \dots + w_k \]

左侧所有中间变量全部发生裂项相消，仅剩下首尾两项：

\[ x_i - x_0 \le \sum_{j=1}^k w_j = \operatorname{Length}(P) \]

代入 \(x_0 = 0\)，得：

\[ x_i \le \operatorname{Length}(P) \]

结论推导： 1. 对任意路径均成立：从 \(0\) 到 \(i\) 的每一条不同路径 \(P\)，都给出了一个形如 \(x_i \le \operatorname{Length}(P)\) 的上限约束； 2. 同时满足所有路径的充要条件：\(x_i\) 必须小于等于所有路径长度的最小值：\(x_i \le \min_{P} \operatorname{Length}(P) = dist[i]\)。

1. 不可超越性与可达性：
2. 若 \(x_i > dist[i]\)，则必然违反最短路径所对应的那条不等式链；
3. 根据最短路的三角不等式性质，令 \(x_i = dist[i]\) 时所有约束恰好全部成立；
4. 因此，\(dist[i]\) 是满足所有不等式约束的前提下，变量 \(x_i\) 所能允许达到的最大可行值（Upper Bound）！

3. 对称性：为什么最长路求解的是最小值？

反之，在求解最小值（下界）时，我们将所有约束化为大于等于号：\(x_i \ge x_j + c\)。从源点 \(0\) 到 \(i\) 的任意一条路径，裂项相消后得到的是一个下限门槛：

\[ x_i \ge x_0 + \operatorname{Length}(P) \]

若存在多条路径（多个下限门槛，如 \(x_i \ge 10, x_i \ge 30, x_i \ge 20\)），要迈过所有门槛，\(x_i\) 必须大于等于最高的那道门槛（最大下限）：

\[ x_i \ge \max(10, 30, 20) = 30 \]

对应的图论算法即为最长路。因此，最长路求解的是满足所有条件时的最小可行值（Lower Bound）。

---

1.4 不等式标准化变换大全 (Cheat Sheet)

在实际做题中，题面给出的不等式形式五花八门，必须熟练统一方向：

原始约束形式	规范化为 \(\le\)（最短路建边）	规范化为 \(\ge\)（最长路建边）	变换技巧说明
标准差分：\(x_i - x_j \le c\)	\(j \xrightarrow{c} i\)	\(i \xrightarrow{-c} j\)	\(x_j - x_i \ge -c\)
反向差分：\(x_i - x_j \ge c\)	\(i \xrightarrow{-c} j\)	\(j \xrightarrow{c} i\)	移项取反
严格小于：\(x_i - x_j < c\)	\(j \xrightarrow{c - 1} i\)	\(i \xrightarrow{-c + 1} j\)	仅限整数域：\(x_i - x_j \le c - 1\)
严格大于：\(x_i - x_j > c\)	\(i \xrightarrow{-c - 1} j\)	\(j \xrightarrow{c + 1} i\)	仅限整数域：\(x_i - x_j \ge c + 1\)
双向等式：\(x_i = x_j\)	\(j \xrightarrow{0} i \quad \land \quad i \xrightarrow{0} j\)	\(j \xrightarrow{0} i \quad \land \quad i \xrightarrow{0} j\)	拆为 \(x_i - x_j \le 0\) 与 \(x_j - x_i \le 0\)
单变量上界：\(x_i \le c\)	\(0 \xrightarrow{c} i\)	\(i \xrightarrow{-c} 0\)	引入虚拟零点 \(x_0 = 0\)
单变量下界：\(x_i \ge c\)	\(i \xrightarrow{-c} 0\)	\(0 \xrightarrow{c} i\)	引入虚拟零点 \(x_0 = 0\)

解的平移不变性 (Shift Invariance)

若 \((x_1, x_2, \dots, x_n)\) 是差分约束系统的一组可行解，则对任意常数 \(C\)，\((x_1 + C, x_2 + C, \dots, x_n + C)\) 也必然是一组可行解。因为每个不等式 \((x_i + C) - (x_j + C) = x_i - x_j \le c_k\) 中的常数 \(C\) 会完全相互抵消。 因此，差分约束系统求解的是变量之间的相对差值。

---

1.5 超级源点 (Super Source) 的必要性

如果图是不连通的（由多个独立的连通块组成），从任意单个节点出发都无法遍历全图，可能会漏判孤立连通块中的负权环。

构建超级源点： 建立一个编号为 \(0\) 的虚拟节点，向所有真实节点 \(1, 2, \dots, n\) 连一条边权为 \(0\) 的有向边：

\[ 0 \xrightarrow{0} i \quad (\forall i \in [1, n]) \]

• 代数含义：相当于在系统中人为追加了 \(n\) 个无害的先验约束 \(x_i - x_0 \le 0 \iff x_i \le x_0\)；
• 图论作用：确保超级源点 \(0\) 能够到达图中的每一个顶点，使得一次 SPFA 遍历即可排查全图任何角落隐藏的负权环。

---

2. SPFA 判负环与求解标准模板

差分约束系统中最通用的求解算法是 SPFA（基于队列优化的 Bellman-Ford）。

核心判定逻辑：

• 维护 count[u] 数组：记录从源点到节点 \(u\) 的最短路径上经过的边数；
• 若某个节点的 count[u] >= n + 1（图包含 \(n\) 个真实节点加 \(1\) 个超级源点，共 \(n+1\) 个顶点），说明最短路径包含了至少 \(n+1\) 条边、经过了 \(n+2\) 个节点。根据鸽巢原理，路径上必然出现了重复节点，即检测到负权环（系统无解）！

#include <vector>
#include <queue>
#include <limits>

struct Edge {
    int to;
    int weight;
};

class DifferenceConstraints {
public:
    int n; // 变量数量 (1 到 n)
    std::vector<std::vector<Edge>> adj;

    DifferenceConstraints(int n) : n(n), adj(n + 1) {}

    // 添加约束: x_u - x_v <= weight (即从 v 到 u 连一条权为 weight 的边)
    void add_constraint(int v, int u, int weight) {
        adj[v].push_back({u, weight});
    }

    // 求解可行解。若存在负环返回 false，否则返回 true 并将解保存在 result 中
    bool solve(std::vector<int>& result) {
        // 1. 建立超级源点 0，向所有顶点连边权为 0 的边
        for (int i = 1; i <= n; ++i) {
            adj[0].push_back({i, 0});
        }

        const int INF = 1e9;
        std::vector<int> dist(n + 1, INF);
        std::vector<int> count(n + 1, 0);
        std::vector<bool> in_queue(n + 1, false);
        std::queue<int> q;

        dist[0] = 0;
        q.push(0);
        in_queue[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;

            for (const auto& edge : adj[u]) {
                int v = edge.to;
                int w = edge.weight;

                // 松弛操作 (寻找最短路)
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    count[v] = count[u] + 1;

                    // 顶点总数为 n + 1 (包含超级源点 0)
                    // 最短路边数达到 n + 1 说明存在负权环
                    if (count[v] >= n + 1) {
                        return false; // 系统无解
                    }

                    if (!in_queue[v]) {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }

        // 提取可行解 (1 到 n)
        result.assign(dist.begin() + 1, dist.end());
        return true;
    }
};

---

3. 经典应用模型与建模套路

3.1 模型一：连续区间计数与前缀和转化 (Interval Coverage)

问题特征：在数轴 \([0, M]\) 上选点，要求每个给定的区间 \([L_i, R_i]\) 内部至少包含 \(C_i\) 个被选点，求整条数轴上最少需要选择多少个点。

差分约束建模密码：

设 \(S[k]\) 表示在区间 \([0, k]\) 内被选取的点的总数（前缀和）。

1. 区间限制条件：区间 \([L_i, R_i]\) 至少有 \(C_i\) 个点： \(S[R_i] - S[L_i - 1] \ge C_i \iff S[R_i] \ge S[L_i - 1] + C_i\)
2. 离散点的天然物理约束（隐藏约束）： 每个位置要么选（贡献 1），要么不选（贡献 0）： \(0 \le S[k] - S[k - 1] \le 1 \quad (\forall k)\)
3. \(S[k] - S[k - 1] \ge 0 \iff S[k] \ge S[k - 1] + 0\)
4. \(S[k] - S[k - 1] \le 1 \iff S[k - 1] \ge S[k] - 1\)
5. 目标：求 \(S[M] - S[-1]\) 的最小值。建立最长路模型，从起点出发跑 SPFA 最长路，终点的距离即为全局最少选点数！

---

3.2 模型二：DAG 偏序拓扑与分层定值

问题特征：若题目中的约束全为严格大于/小于（如 \(x_i > x_j \iff x_i - x_j \ge 1\)），且边权全为非负常数。

• 退化特性：如果图中没有负环，且所有边权为正，那么这本质上是一个 有向无环图 (DAG)。
• 极速优化：无需使用较慢的 SPFA，直接在 DAG 上运行 拓扑排序 (Kahn 算法)，按拓扑序进行动态规划（DP 最长路）： \(dist[v] = \max(dist[v], dist[u] + 1)\) 时间复杂度直接从 \(\mathcal{O}(V E)\) 优化至线性 \(\mathcal{O}(V + E)\)！

---

4. LeetCode 经典真题精选与深度精析

• LeetCode 2589 - 完成所有任务的最少时间 (Minimum Time to Complete All Tasks) 困难

  提示

  差分约束区间选点模型的 1:1 原型题。

  • 模型转化：
  • 设 \(s[i]\) 为时间点 \([0, i]\) 内电脑累计运行的总时间（前缀和）。
  • 每个任务 \([start, end, duration]\) 要求：\(s[end] - s[start - 1] \ge duration\)。
  • 每一秒要么运行要么休息：\(0 \le s[i] - s[i - 1] \le 1\)。
  • 解法一（差分约束 SPFA 最长路）：
  • 建边：\((start - 1) \xrightarrow{duration} end\)，\((i - 1) \xrightarrow{0} i\)，\(i \xrightarrow{-1} (i - 1)\)。
  • 跑最长路求 \(s[\max(end)]\)。
  • 解法二（贪心反悔/区间贪心）：
  • 鉴于数据范围较小（时间点 \(\le 2000\)），按右端点升序排序，优先在区间靠后的位置开启运行，以最大化被后续任务复用的概率。
  • 时间复杂度：贪心为 \(\mathcal{O}(N \log N + N \cdot L)\)，差分约束为 \(\mathcal{O}(V E)\)。

• LeetCode 2392 - 给定条件下构造矩阵 (Build a Matrix With Conditions) 困难

  提示

  二维解耦的偏序差分约束与拓扑排序。

  • 问题本质：
  • 给定行限制 [above, below]，要求 \(row_{above} < row_{below}\)；
  • 给定列限制 [left, right]，要求 \(col_{left} < col_{right}\)。
  • 差分约束视角：
  • 行列完全独立，可解耦为两个一维子问题。
  • 每个限制等价于整数差分约束：\(row_{below} - row_{above} \ge 1\)。
  • 因为权值全为正数且求任意合法排布，若存在可行解则必无环。
  • 拓扑排序求解：
  • 对行条件与列条件分别建图，执行两次拓扑排序。
  • 若任一图存在环（Kahn 算法遍历点数 \(< k\)），则差分约束无解返回空矩阵。
  • 否则根据拓扑序直接确定每个数字在矩阵中的行号与列号。
  • 时间复杂度 \(\mathcal{O}(k + \text{edges})\)，空间复杂度 \(\mathcal{O}(k + \text{edges})\)。

• LeetCode 2050 - 并行课程 III (Parallel Courses III) 困难

  提示

  DAG 差分约束最长路（关键路径 CPM 模型）。

  • 模型映射：
  • 设 \(finish[i]\) 为完成第 \(i\) 门课程的最早时刻。
  • 先修关系 \([prev, next]\) 意味着：\(finish[next] - finish[prev] \ge time[next]\)。
  • 这是典型的标准最长路差分约束系统。
  • DAG 极速递推：
  • 题目保证图为 DAG。
  • 拓扑排序结合 DP：\(finish[v] = \max(finish[v], finish[u] + time[v])\)。
  • 最终答案为 \(\max_{i=1}^n finish[i]\)。
  • 时间复杂度 \(\mathcal{O}(V + E)\)，空间复杂度 \(\mathcal{O}(V + E)\)。

• LeetCode 785 - 判断二分图 (Is Graph Bipartite?) 中等

  提示

  模 2 域下的奇偶差分约束系统。

  • 模型分析：
  • 每条无向边 \((u, v)\) 要求两端点颜色不同，即在模 2 意义下满足： \(color[u] - color[v] \equiv 1 \pmod 2\)。
  • 差分约束在模 2 域下的无解条件即为：图中存在奇数长度的环（奇环）。
  • 求解算法：
  • BFS / DFS 二染色，或带权并查集维护模 2 偏移量。
  • 时间复杂度 \(\mathcal{O}(V + E)\)，空间复杂度 \(\mathcal{O}(V)\)。

• 洛谷 P5960 - 【模板】差分约束算法 普及+/提高

  提示

  标准差分约束模板题。

  • 包含 \(n\) 个变量与 \(m\) 个形如 \(x_u - x_v \le y\) 的不等式。
  • 建立超级源点 \(0 \xrightarrow{0} i\)，运行 SPFA 判定负环。若有负环输出 NO，否则输出一组解 \(dist[1 \dots n]\)。