use*_*258 1 algorithm graph-theory graph-algorithm
从杰夫·埃里克森的讲义上的图形算法，有一个锻炼，以检查是否给定顶点之间的步行路程s，并t可以通过3有向图整除。
我的想法是在图上使用广度优先搜索来获取从s到 的所有路径t。如果简单路径的长度不能被 3 整除，则再次运行该算法以检查循环长度不能被 3 整除的位置s和t位置之间是否存在循环。但是，我觉得该方法非常低效。
如果您对这个问题有任何好的建议，那就太好了。
这类问题通常可以通过改变图形和应用标准算法来解决，而不是改变算法。
在这种情况下，我们可以创建一个每个节点的三个副本的新图，例如，如果u是原始图中的一个节点，则新图具有三个对应的节点(u, 0)，(u, 1)和(u, 2)。对于每个边缘u ? v在原来的曲线图中，新的图形具有三个相应的边缘(u, 0) ? (v, 1)，(u, 1) ? (v, 2)和(u, 2) ? (v, 0)。
给定(n_0, r_0) ? ... ? (n_k, r_k)带k边的步行，我们知道r[i+1] = r[i] + 1 (modulo 3)，因为新图中的所有边都满足该属性。因此如果r_0 = 0那么r_k = k (modulo 3).
由此可见，(s, 0)有步行(t, 0)的，当且仅当新的图s有一个步行t在原始图使用的3个边的整数倍。所以你可以在新图中应用一个标准的寻路算法，比如 BFS，看看是否(t, 0)可以从(s, 0).
请注意，如果您必须实际将其实现为代码，则没有必要将新图实际构建为数据结构；它是一个隐式图。