拨号关系的补全: 题解¶
思路与贡献¶
把初始关系看成函数图：每个顶点恰有一条出边 \(i\to a_i\) .合法补全存在，当且仅当所有有向环的长度都不超过二。
标准程序保留出题人的时间戳遍历、环上点计数以及扣除一元环和二元环的方法。Codex（GPT-6）整理 C++17 实现，并补充通过全序扩张构造格的充分性证明。程序见 std.cpp，另有入度剥离解法。
判定条件的证明¶
必要性。 假设存在长度至少为三的有向环。沿环传递可推出每条环边的反向关系。由于每个顶点只有一条初始出边，这条反向关系原来不存在。它必须被新加入，违反限制，因此不能补全。允许多个符号表示同一元素也无法避免这一点，因为同一元素对应的双向关系仍必须都出现。
充分性。 假设环长只有一或二。把每个二元环中的两个符号合并成同一元素；其余符号各自成为一个元素。收缩后去掉自环，所得图没有有向环。取它的一个拓扑序，按此顺序把所有元素排成全序，并把全序中所有不大于关系加入符号关系。
有限非空全序是格：任意两个元素的较大者是上确界，较小者是下确界。不同元素之间的初始边都沿拓扑序向前，其反向关系不会出现。同一元素内部，二元环的两个方向已经存在，自环也已存在，所以没有新加任何被禁止的反向关系。每个元素都有符号表示，满足满射要求。因此构造合法。
时间戳算法¶
给每个首次访问的顶点一个不断递增的编号。从一个未访问顶点出发时，记录本次起始编号 \(Begin\) ，沿出边走到已访问顶点 \(v\) .
- 若 \(Number_v<Begin\) ，说明进入了以前处理过的路径，本次没有新环。
- 否则 \(v\) 在当前路径上。当前计数器为 \(Timer\) ，新环长度就是 \(Timer-Number_v+1\) .
每个环只会在第一次进入时被计数。汇总所有环上顶点数，然后对每个满足 \(a_{a_i}=i\) 的顶点减一。这个等式恰好刻画自环或二元环中的顶点，故剩余计数为零当且仅当没有更长的环。每个测试使用独立数组，支持多组规模先增后减的数据。
复杂度¶
每个顶点首次遍历一次，最后扫描一次，单组时间 \(O(N)\) 、空间 \(O(N)\) .整份文件时间为 \(O(T+\sum N)\) .不需要实际构造稠密的补全关系。