algorithm - Tarjan算法:时间复杂度和轻微修改的可能性

这个问题与one recently asked here有关，但不相同。
我刚读了Wikipedia psuedocode。

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)

    // Consider successors of v
    for each (v, w) in E do
      if (w.index is undefined) then
        // Successor w has not yet been visited; recurse on it
        strongconnect(w)
        v.lowlink  := min(v.lowlink, w.lowlink)
      else if (w is in S) then
        // Successor w is in stack S and hence in the current SCC
        v.lowlink  := min(v.lowlink, w.index)
      end if
    end for

    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        add w to current strongly connected component
      until (w = v)
      output the current strongly connected component
    end if
  end function

显然，我不应该完全理解它，因为我有两个非常基本的问题：
当我们说“cc>”时，这个操作不是O（n）还是至少O（Logn）的复杂性，因为元素应该用它们的索引排序？我们必须为从根节点访问的每个新节点执行此操作，所以总体复杂度if (w is in S)不是。此外，s是一个堆栈，因此在概念上只有顶层元素应该是可访问的，我们如何在其中实现搜索？二进制搜索树不应该是更好的数据结构吗？
在本部分中：
否则，如果（w在s中），则
v.lowlink：=最小值（v.lowlink，w.index）
使用O(NlogN)和不使用w.index是否有特定的原因？使用w.lowlink的好处是它可以回答前面的问题（链接的问题）SCC中所有节点的w.lowlink将保证所有节点的相同。

最佳答案

1）你的第一个问题：它可以在O（1）中轻松完成，只需维护一个布尔数组inStack，矩节点n被放入堆栈中，将inStack[n]标记为true从堆栈中弹出时，将其标记为false。
2）w.index和w.lowlink之间没有太大区别，但这更容易理解，因为我们将理解，这种情况是从节点a->b->c->a检查案例，这将检查节点c何时可以到达前置节点a。请记住，在我们更新C时，节点A lowlink尚未正确更新。
tarjan算法基于这样一个事实：如果并且仅当从该节点到达任何前一节点时，该节点将是scc的根节点（这意味着它在其scc中具有最低的lowlink，并且也等于该节点的索引）。所以这个条件是以最直接的方式实现的，如果我们遇到一个已经被访问过的节点，我们检查这个节点是否是当前节点的前一个（这是由它的索引决定的，也是图中这个节点的级别）