求判断简单图中是否存在同胚于K5/K3,3子图的高效C++算法

核心思路：避开全边枚举，用预处理+定向顶点子集检测+Tarjan扩展算法 #

• 先做图简化：正确处理2度顶点的边收缩
  你之前的操作误区在于“移除2度顶点后直接连接邻接点”——正确的方式是边收缩：遍历所有度数为2的顶点v，找到它的两个邻居u和w，将u的邻接表中v替换为w，w的邻接表中v替换为u，然后标记v为已收缩（后续所有操作忽略该顶点）。递归执行直到没有2度顶点。这样处理后，同胚于K5/K3,3的子图会被简化为K5或K3,3本身，后续校验难度大幅降低。

• 定向枚举顶点子集，而非全边子集
  既然K5依赖5个核心顶点，K3,3依赖6个核心顶点，直接枚举原图中所有5顶点子集和6顶点子集即可：

  • 对5顶点子集：取出这5个顶点及它们之间的所有路径（路径中间顶点必须是已收缩的2度顶点），检查收缩后是否形成K5——即任意两个核心顶点之间要么有直接边，要么通过2度顶点的路径可收缩为直接边。
  • 对6顶点子集：尝试将其划分为两个3顶点分组，检查分组内部顶点间无有效路径（或路径无法收缩为直接边），而两个分组间的每个顶点对都有可收缩为直接边的路径，满足条件即为K3,3的同胚子图。
    15选5共3003种情况，15选6共5005种，加起来仅8000多组，完全能在数分钟内跑完，甚至更快。

• 用Tarjan平面性算法的扩展版直接定位Kuratowski子图
  Tarjan的平面性检测算法本身就能在发现图非平面时，回溯找到导致非平面的Kuratowski子图结构：

  1. 算法基于DFS构建DFS树，通过维护双连通分量和冲突边检测平面性。
  2. 当检测到冲突时，回溯收集相关边和顶点，构造出最小非平面子图，该子图经2度顶点收缩后即为K5或K3,3。
  3. 在Tarjan算法基础上加入冲突路径记录逻辑，提取子图顶点集合后，通过逆收缩（还原之前去掉的2度顶点）得到原图中的同胚子图，再判断其类型。

代码实现注意点 #

• 用邻接表存储图，为每个顶点保留原始编号和收缩标记，避免混淆。
• 执行边收缩时，用bool数组或哈希表记录顶点对间的边，避免重复添加。
• 枚举顶点子集时，用递归或位掩码生成所有5/6顶点组合，避免重复计算。

内容的提问来源于stack exchange，提问作者Relja Šegvić