问题核心

我们需要维护一个随时间增长的有向图，每次添加一条边后，判断是否存在一个经过特殊节点的环。特殊节点是指编号为 $0, 1, \dots, k-1$ 的星球。

关键限制：

• 初始时已有 $k-1$ 条起始传送器：$(0,1), (1,2), \dots, (k-2,k-1)$
• 每次添加一条新边 $(u,v)$
• 需要判断添加后是否存在包含特殊节点的环

---

问题转化

"能获得无穷多枚邮票" ⇔ 存在一个包含至少一个特殊节点的环

因为：

• 游客可以从任一星球出发
• 每次进入特殊星球获得邮票
• 如果存在包含特殊节点的环，就可以无限循环获得邮票

---

算法思路

1. 关键观察

由于起始传送器 $(0,1), (1,2), \dots, (k-2,k-1)$ 的存在，所有特殊节点已经形成一个链：

$$0 \to 1 \to 2 \to \dots \to k-1$$

这意味着：

• 如果存在从某个节点 $v$ 到特殊节点 $0$ 的路径，那么可以从 $0$ 走到 $k-1$
• 如果存在从 $k-1$ 回到某个特殊节点的路径，就形成了环

---

2. 核心判断条件

存在包含特殊节点的环 ⇔ 存在一条从某个特殊节点回到特殊节点集合的路径

更具体地说，以下任一条件成立：

1. 自环：存在特殊节点 $u$ 且有边 $(u,u)$
2. 小环：存在边 $(u,v)$ 其中 $u,v$ 都是特殊节点且 $v \leq u$（因为特殊节点已形成递增链）
3. 大环：存在路径从 $k-1$ 回到 $0$（这样形成 $0\to 1\to\dots\to k-1\to 0$ 的环）

---

3. 算法框架

我们需要维护两种可达性信息：

(1) 从特殊节点集合出发能到达的节点

• 维护集合 $R$：能从特殊节点到达的所有节点
• 当添加边 $(u,v)$ 时，如果 $u \in R$，则 $v$ 也加入 $R$

(2) 能到达特殊节点集合的节点

• 维护集合 $S$：能到达特殊节点的所有节点
• 当添加边 $(u,v)$ 时，如果 $v \in S$，则 $u$ 也加入 $S$

---

4. 环检测策略

每次添加边 $(u,v)$ 后，检查以下条件：

1. 直接自环：$u$ 是特殊节点且 $u = v$
2. 逆向环：$u,v$ 都是特殊节点且 $v \leq u$（破坏递增性）
3. 大环形成：$u \in R$ 且 $v \in S$（形成从特殊节点出发又回到特殊节点的路径）

其中第3种情况最复杂，需要维护 $R$ 和 $S$ 集合。

---

高效实现方案

数据结构选择

• R集合（从特殊节点可达）：使用 BFS/DFS 动态维护
• S集合（可达特殊节点）：使用反向图的 BFS/DFS 动态维护

具体算法步骤

1. 初始化：

   • 建立正向图 $G$ 和反向图 $G'$
   • 将特殊节点 $0,1,\dots,k-1$ 加入 $R$ 和 $S$
   • 初始边 $(i,i+1)$ 加入图

2. 处理添加边 $(u,v)$：

   • 将边加入正向图和反向图
   • 检查条件1和2，如果满足直接返回1
   • 如果 $u \in R$，从 $v$ 开始 BFS 扩展 $R$ 集合
   • 如果 $v \in S$，从 $u$ 开始 BFS 扩展 $S$ 集合（在反向图上）
   • 检查新扩展的节点中是否存在 $R \cap S \neq \emptyset$，如果存在则返回1

3. 优化：使用队列进行增量 BFS，避免重复遍历

---

复杂度分析

• 空间复杂度：$O(n+m)$ 存储图和集合
• 时间复杂度：每个节点和边最多被遍历常数次，总体 $O(n+m)$
• 可行性：$n \leq 3\times 10^5, m \leq 5\times 10^5$ 完全可行

---

特殊情况处理

样例1分析

• 初始：$0\to1\to2$（特殊节点链）
• 添加 $(1,4)$ 时：
  • $1 \in R$（从特殊节点可达）
  • 检查是否能回到特殊节点：$4\to5\to0$，$0$ 是特殊节点
  • 因此 $4 \in S$（能到达特殊节点）
  • 形成环：$1\to4\to5\to0\to1$

样例2分析

• 添加 $(1,1)$：自环，直接返回1

样例3分析

• 添加 $(3,2)$ 时：
  • $3$ 不在初始 $R$ 中
  • 但 $2$ 是特殊节点，所以 $3$ 加入 $S$
  • 后续添加边时可能形成环

---

算法正确性

充分性

如果算法返回1，一定存在包含特殊节点的环：

• 条件1、2显然成立
• 条件3：$u \in R$ 且 $v \in S$ ⇒ 存在路径从特殊节点到 $u$，从 $v$ 到特殊节点，加上边 $(u,v)$ 形成环

必要性

如果存在包含特殊节点的环，算法一定会返回1：

• 环上至少有一个特殊节点
• 沿着环遍历，一定会遇到某个边 $(u,v)$ 使得 $u \in R$ 且 $v \in S$

---

总结

这道题的核心是动态维护双向可达性信息：

1. 正向可达性（R集合）：从特殊节点能到达哪些节点
2. 反向可达性（S集合）：哪些节点能到达特殊节点
3. 环检测：$R \cap S \neq \emptyset$ 时存在环

通过增量 BFS 维护这两个集合，在 $O(n+m)$ 时间内解决了动态图判环问题，巧妙利用了特殊节点初始形成链的特性来简化判断条件。