有向图上的弗洛伊德循环检测算法

Question

如何使用Floyd循环检测算法来计算有向图中的循环长度?我遇到的大多数链接都是在链表上解释Flyod的循环算法，但是如何将相同的算法用于有向图呢?

Answer 1

当两个指针相互到达时，此时指针a已经走了k步，指针b已经走了2k步，所以循环的长度除以k，将指针a移动到节点x，一步步向前推进，直到它们再次相遇，就可以找到属于循环的第一个节点。

a = x;
while (a != b) {
a = succ(a);
b = succ(b);
}
first = a;

之后，循环的长度可以计算如下:

b = succ(a);
length = 1;
while (a != b) {
b = succ(b);
length++;
}

参考:《竞争性编程指南:通过竞赛学习和改进算法》作者:Antti laaksonen