在彩色图中查找具有单个不同颜色边的循环

Question

给定一个边上有红/蓝着色的一般无向图，我希望能够检测到图中恰好包含一条蓝色边的所有循环。有已知的算法吗？

我知道如何使用DFS方法检测普通图中的循环，一旦找到循环，我可以通过回溯和计数蓝边的数量来检测单个蓝边循环，但据我所知，这种解决方案会导致边缘二次型时间复杂性。还有更好的吗？

Answer 1

要检测是否存在一个只有一条蓝色边的循环，请查找由红色边组成的子图的连接组件。对于每个蓝色边，测试其端点是否位于相同的红色连接组件中。如果它们这样做了，那么就存在这样一个循环，由蓝色边和DFS指定为树边的边的生成林中其端点之间的路径形成。

相反，假设存在这样一个循环。循环的红色部分确保蓝色边的端点属于同一个零部件。