如何证明一个线性算法，该算法能识别图中的所有圈和长度，其中每个顶点正好有一个输出边。

Question

考虑n个顶点上的有向图，其中每个顶点正好有一个输出边。这个图包括一个循环集合以及具有到圈的路径的附加顶点，我们称之为分支。描述一个识别所有循环并计算每个周期长度的线性时间算法。您可以假设输入是以数组A的形式给出的，其中Ai是i的邻居，因此图具有边(i，Ai)。

到目前为止，我对算法的方法基本上是标记我遍历过的顶点，每次一个顶点指向我遍历过的顶点，我就数一个循环，然后再转到下一个未访问的顶点。在这个过程中，我还有一个hashmap或者什么东西来记录每个节点被遍历的顺序，这样每当我识别一个循环时，我就可以计算出长度。(这是线性的吗？)然而，我对证明非常新，我不知道如何证明一个算法的正确性。

Answer 1

如果允许您使用额外的内存，Python中的算法将是这样的。

colors = [0] ** N; # initialize N element array withe values of zero (not seen)
for i in range(N):
    v = i # current vertex
    if colors[v] != 0: continue # already seen
    colors[v] = 1 # seen
    v = A[v] # move to neighbor
    while colors[v] == 0:
       colors[v] = 1
       v = A[v] # move to neighbor
    # we have reached previously seen node; this is the start node of a cycle
    colors[v] = 2 # mark the start of a cycle
    cycle_len = 1
    v = A[v] # move to neighbor
    while colors[v] == 1:
       cycle_len += 1
       v = A[v] # move to neighbor
   print("got a cycle with length =", cycle_len)

其基本思想是使用三种颜色对已经访问过的节点和作为循环起点的节点进行不同的标记；显然，单个节点只能属于单个周期。

该算法是线性的，因为内部while循环只对以前未见过的节点执行。跳过已经看到的节点。在最坏的情况下，两个内部while循环都完全执行，但2*N仍然是O(N)。

使用hashmap不符合要求，因为hashmap的最坏情况时间复杂度不是线性的。