平面连通图面识别算法异常：多识别一个面的求助

核心排查方向 #

1. 检查有向边的访问标记逻辑 #

• 确认每条无向边对应的两条有向边，在DFS遍历中是否被成对标记为已访问。如果某条有向边未被正确标记，可能会被重复遍历，生成一个虚假的闭合面。
• 验证方式：把第三个测试用例输出的7个面全部打印出来，找出那个多余的面，检查它的边序列是否存在重复使用的有向边，或者是否是一条来回走的无效边序列（比如仅包含两条互逆的有向边）。

2. 验证顶点邻边的逆时针排序正确性 #

• relativeInclination用arctan计算倾角存在天生缺陷：arctan的返回范围是(-π/2, π/2)，无法区分第二、三象限的角度，会导致邻边排序错误。应该改用atan2(dy, dx)获取(-π, π)范围内的完整角度，再基于上一条边的反向作为参考，计算相对倾角排序。
• 验证方式：取测试用例中出问题的起始顶点，手动列出其所有邻边的逆时针顺序，和sort_connections函数的输出对比，重点检查共线边、接近水平/垂直边的排序结果。

3. 检查DFS的面合法性判断逻辑 #

• 确认DFS终止条件是否严格：只有当遍历回到起始顶点，且边序列长度≥3时，才应被计数为一个合法面。如果终止条件过松（比如回到起点但边数不足3），会生成无效的假面。
• 额外检查：是否把外部无限面重复计数了——比如算法在不同起始点触发了两次外部面的遍历，导致多算一个。

4. 排查起始点相关的遍历差异 #

• 针对“问题与起始点相关”这一特征：
  • 检查问题起始点的邻边是否有特殊情况（比如度数为2、存在共线边）；
  • 确认DFS在起始点的初始化逻辑是否正确——比如是否错误地重复处理了起始点的第一条边，或者遗漏了某条边的遍历；
  • 验证起始点所在的边是否被其他面正确覆盖，是否存在“孤立”的边被单独识别成一个面。

5. 用欧拉公式验证测试用例的正确性 #

• 严格平面连通图满足欧拉公式：V - E + F = 2（其中F包含外部无限面）。计算第三个测试用例的顶点数V、边数E，代入公式算出理论面数F=E-V+2，确认预期的6个面是否正确。如果理论值和预期不符，可能是测试用例的预期本身错误。

内容的提问来源于stack exchange，提问作者Nicolas Von Dolinger