# 拨号关系的补全: 补充解法

## 入度剥离

Codex（GPT-6）补充这个线性算法及 [alternative.cpp](alternative.cpp)。合法性判据及充分必要证明见[主题解](solution.zh.md)：只需排除长度至少为三的环。

计算所有顶点入度，把入度为零的顶点入队。反复弹出一个顶点，将其唯一后继的入度减一；后继入度变零时继续入队。最后扫描未被移除的顶点，要求每个都满足 $a_{a_i}=i$ .全部满足输出 `Y` ，否则输出 `N` .

环上每个顶点始终至少有来自环中前驱的一条入边，所以不会被剥离。函数图中所有非环顶点构成指向环的树，沿叶到根依次都被移除。因此剩余顶点恰为全部环顶点。在它们中，$a_{a_i}=i$ 恰好说明所在环长为一或二，算法与判据等价。

单组时间和空间均为 $O(N)$ ；全文件时间为 $O(T+\sum N)$ .相比时间戳遍历，本方法增加入度数组和队列，换取直接的剥离不变量；没有渐进复杂度优势。