如何证明一种线性算法，该算法可在图中每个顶点恰好具有一个输出边的图中标识所有周期和长度

Question

考虑n个顶点上的有向图，其中每个顶点都具有一个向外的边缘。该图由一系列周期组成以及具有通往循环的路径的其他顶点，我们打电话给分支机构。描述一个线性时间算法来识别所有周期并计算每个周期的长度。您可以假设输入以数组A给出，其中A [i]是i的近邻，因此图具有边（i，A [i]）。

到目前为止，我对该算法的方法基本上是标记我遍历的顶点，每当一个顶点指向我遍历的顶点时，我都会计算一个周期并转到下一个未访问的顶点。在此过程中，我还具有一个哈希图或某种东西来记录遍历每个节点的顺序，以便每当标识一个循环时就可以计算长度。 （这是线性的吗？）但是，我对证明还很陌生，不知道如何证明算法的正确性。

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 = 0
    while colors[v] == 1:
       cycle_len += 1
       v = A[v] # move to neighbor
   print("got a cycle with length =", cycle_len)

[基本思想是使用三种颜色来不同地标记已经访问过的节点和作为循环起点的节点（显然，单个节点只能属于一个循环）。