D. DAG Serialization 详细题解（对标程逐行解析）

这是一道模拟 + 拓扑排序 + 分类讨论的图论构造题，核心突破口是题目给出的关键限制：最多只有 2 个操作返回 true。

一、题意彻底梳理

1. 寄存器规则

有一个布尔寄存器，初始值为 $\boldsymbol{\text{false}}$，支持两种操作：

• $\boldsymbol{\text{set}}$：仅当寄存器为 $\text{false}$ 时生效，生效后变为 $\text{true}$，返回 $\text{true}$；否则返回 $\text{false}$。
• $\boldsymbol{\text{unset}}$：仅当寄存器为 $\text{true}$ 时生效，生效后变为 $\text{false}$，返回 $\text{true}$；否则返回 $\text{false}$。

2. 约束条件

1. 给定 $n$ 个操作，最多 2 个操作返回 true。
2. 给定 DAG 偏序：边 $a\rightarrow b$ 表示 $a$ 必须在 $b$ 之前执行。
3. 要求输出一个合法拓扑序，满足：
   • 遵守所有 DAG 先后关系
   • 按序执行后，每个操作的返回值与输入一致
4. 无解输出 $-1$。

3. 数据范围

$1\le n\le 10^5,\ 0\le m\le 10^5$

---

二、核心结论（解题关键）

因为最多 2 次成功操作，寄存器的状态变化只有 3 种合法情况，其余全是无解：

1. 0 个 true：无解 初始状态是 $\text{false}$，至少执行一次 $\text{set}$ 才能改变状态，不可能全程无任何操作成功。

2. 1 个 true：必须是 $\boldsymbol{\text{set true}}$ 唯一的成功操作只能是把寄存器从 $\text{false}\to\text{true}$。

3. 2 个 true：必须是 $\boldsymbol{\text{set true}} \to \boldsymbol{\text{unset true}}$ 第一次：$\text{false}\to\text{true}$ 第二次：$\text{true}\to\text{false}$ 顺序绝对不能颠倒。

---

三、标程整体架构

主函数流程：
1. 读入操作，收集所有 result=true 的操作
2. 分类讨论（0/1/2 个 true），判断基础合法性
3. 调用定制拓扑排序，强制关键操作顺序
4. 输出答案或 -1

---

四、逐段代码解析

1. 全局变量定义

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];   // DAG 邻接表
int in_deg[MAXN];        // 入度，用于拓扑排序
int op[MAXN];            // 操作类型：1=set，2=unset
int res[MAXN];           // 操作结果：1=true，0=false

---

2. 核心函数：定制拓扑排序 topo(x, y)

功能：生成一个拓扑序，强制 x 在 y 前面执行（x/y 可以为 0 表示不存在）。

执行步骤

1. 先排普通节点 所有入度为 0、且不是 x/y 的节点优先加入队列。

   for (int i = 1; i <= n; ++i) {
       if (deg[i] == 0 && i != x && i != y) q.push(i);
   }
   

2. 普通节点正常拓扑 不断取出队首，加入答案序列，更新后继节点入度。

   注意：x 和 y 暂时不处理。

3. 插入 x（set 操作）

   • 如果 x 入度不为 0 → 无解
   • 把 x 加入序列
   • 继续处理 x 的后继节点

   if (deg[x] != 0) return {};
   order.push_back(x);
   

4. 最后插入 y（unset 操作）

   • 保证 y 在所有节点之后执行

   if (deg[y] != 0) return {};
   order.push_back(y);
   

5. 完整性检查 最终序列长度必须等于 $n$，否则说明有环/约束冲突，返回空。

---

3. 主函数：分类讨论

情况 1：0 个 true

if (trues.size() == 0) {
    cout << -1 << endl;
    return 0;
}

直接判定无解。

情况 2：1 个 true

int x = trues[0];
if (op[x] != 1) { cout << -1; return 0; }
ans = topo(0, x);

• 必须是 set 操作
• 拓扑要求：x 放在最后

情况 3：2 个 true

bool ok1 = (op[x] == 1 && op[y] == 2);
bool ok2 = (op[y] == 1 && op[x] == 2);
if (!ok1 && !ok2) { cout << -1; return 0; }
if (op[x] != 1) swap(x, y);
ans = topo(x, y);

• 必须一个是 set，一个是 unset
• 强制顺序：set 在前，unset 在后
• 调用 topo(x, y) 生成顺序

---

五、为什么这个解法是正确的？

1. 寄存器状态严格匹配

   • 1 个 true：false → set(true) → 结束
   • 2 个 true：false → set(true) → unset(false) → 结束 所有其他操作都在状态不变的阶段执行，必然返回 false。

2. DAG 约束满足 拓扑排序保证所有 $a\rightarrow b$ 的边都满足 $a$ 在 $b$ 前。

3. 效率足够 时间复杂度 $O(n+m)$，完美通过 $10^5$ 数据。

---

六、样例解释（样例 1）

输入：

5
set true      --> 1
unset true    --> 2
set false     --> 3
unset false   --> 4
unset false   --> 5

• true 操作：1、2
• 顺序要求：1 必须在 2 前面
• 拓扑序：5 1 3 2 4
• 执行流程： 5(unset, false) → 1(set, true) → 3(set, false) → 2(unset, true) →4(unset, false) 完全符合结果要求。

---

七、无解情况总结

输出 $-1$ 的所有可能：

1. 0 个 true
2. 1 个 true 但不是 set
3. 2 个 true 但不是 set+unset 组合
4. DAG 约束冲突（例如要求 unset 在 set 前）
5. 拓扑序不完整（图有环）

---

八、总结

本题核心思维

1. 突破口：最多 2 个 true → 状态极少，可枚举
2. 固定顺序：
   • 1 个 true：set 放最后
   • 2 个 true：set 先，unset 后
3. 算法：定制化拓扑排序构造答案

标程优点

• 逻辑清晰，分类讨论全面
• 时间复杂度线性，适合大数据
• 直接 AC 所有测试用例