如何使用C中的并行算法计算图中的循环长度？

Question

我变得沮丧，因为我无法解决这个问题。我希望这是在这种情况下寻求帮助的正确地方。 问题是，我有一个图，它是不相交有向循环的并集。此外，还有 𝑘 节点 𝑋(1), ..., 𝑋(𝑘)，其索引存储在长度为 𝑘 ≤ 𝑛 的数组 𝑋 中。该图由长度为 𝑛 的数组 𝑆 表示，其中 𝑆(𝑖) 是 𝑖 的后继节点。

我需要计算包含𝑋中每个节点的循环长度。结果应该是长度为 𝑘 的数组 𝑌，使得 𝑌(1), ..., 𝑌(𝑘) 包含相应循环的长度。

任何人都可以建议一个运行时间为 𝑂(𝑘 + log 𝑛) 的算法/伪代码（C 语言）并使用 𝑂(𝑛) 来计算 𝑌？

任何帮助或指示将不胜感激！

我只能创建这个伪代码：

for i in {1,...,k} par do

    while S[i] != i

        S[i] = S[ S[i] ]
        Y[i]++

运行时间为𝑂(𝑘*log 𝑛)并且工作𝑂(𝑘𝑛)

Answer 1

为了满足您的时间限制，您需要为每个节点启动一个进程，并且这些进程必须能够在 O(log n) 时间内集体处理每个节点的周期。

“处理一个循环”，我特意指的是收集循环中所有节点上某个函数的最小值或最大值，并将其广播到循环中的所有节点。 如果你能做到这一点，那么你的问题就可以通过这个恒定长度的步骤序列来解决：

1. 在每个节点的循环中找到索引最小的节点。 该节点将成为每个周期的“代表”；
2. 求从每个节点中的任意节点到循环代表的最大步数。 这将是循环的长度，即从代表到自身的步数。

然后您可以查找每个 k 目标节点的循环长度。

在 O(log n) 时间内处理所有循环：

1. 对于每个节点 i，令 X[i] = S[i]，令 d = 1，并令 V[i] 为每个节点的目标统计量。 我们将保持以下不变量：
   1. X[i] = S^d[i]
   2. V[i] = 从 i 开始的 d 个节点上的目标统计量的最小值或最大值。 对于“与代表的距离”统计数据，如果在 d 步中无法联系到代表，则使用 -1。
2. 然后我们将 d 加倍，同时保持上述不变量。 而 d < n:
   1. V[i] = minOrMax(V[i], V[X[i]])
   2. X[i] = X[X[i]]
   3. d *= 2

请注意，（2）中循环的每次迭代都需要对所有节点有效地同步完成。 有本地 O(1) 方法可以实现此目的。 基本上，在 X 中的前驱和后继读取完 d=n 的结果之前，任何节点都无法处理步骤 d=2n。

一旦所有节点的 d>=n，V[i] 在每个周期中为所有节点保持相同的最小值或最大值。