# 拨号关系的补全: 题解

## 思路与贡献

把初始关系看成函数图：每个顶点恰有一条出边 $i\to a_i$ .合法补全存在，当且仅当所有有向环的长度都不超过二。

标准程序保留出题人的时间戳遍历、环上点计数以及扣除一元环和二元环的方法。Codex（GPT-6）整理 C++17 实现，并补充通过全序扩张构造格的充分性证明。程序见 [std.cpp](std.cpp)，另有[入度剥离解法](solution-alternative.zh.md)。

## 判定条件的证明

**必要性。** 假设存在长度至少为三的有向环。沿环传递可推出每条环边的反向关系。由于每个顶点只有一条初始出边，这条反向关系原来不存在。它必须被新加入，违反限制，因此不能补全。允许多个符号表示同一元素也无法避免这一点，因为同一元素对应的双向关系仍必须都出现。

**充分性。** 假设环长只有一或二。把每个二元环中的两个符号合并成同一元素；其余符号各自成为一个元素。收缩后去掉自环，所得图没有有向环。取它的一个拓扑序，按此顺序把所有元素排成全序，并把全序中所有不大于关系加入符号关系。

有限非空全序是格：任意两个元素的较大者是上确界，较小者是下确界。不同元素之间的初始边都沿拓扑序向前，其反向关系不会出现。同一元素内部，二元环的两个方向已经存在，自环也已存在，所以没有新加任何被禁止的反向关系。每个元素都有符号表示，满足满射要求。因此构造合法。

## 时间戳算法

给每个首次访问的顶点一个不断递增的编号。从一个未访问顶点出发时，记录本次起始编号 $Begin$ ，沿出边走到已访问顶点 $v$ .

- 若 $Number_v<Begin$ ，说明进入了以前处理过的路径，本次没有新环。
- 否则 $v$ 在当前路径上。当前计数器为 $Timer$ ，新环长度就是 $Timer-Number_v+1$ .

每个环只会在第一次进入时被计数。汇总所有环上顶点数，然后对每个满足 $a_{a_i}=i$ 的顶点减一。这个等式恰好刻画自环或二元环中的顶点，故剩余计数为零当且仅当没有更长的环。每个测试使用独立数组，支持多组规模先增后减的数据。

## 复杂度

每个顶点首次遍历一次，最后扫描一次，单组时间 $O(N)$ 、空间 $O(N)$ .整份文件时间为 $O(T+\sum N)$ .不需要实际构造稠密的补全关系。