Этот вопрос связан, но не совпадает содин недавно спросил здесь.

Я просто прочиталВикипедия 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

Я, очевидно, не должен был это правильно понять, поскольку у меня есть два очень простых вопроса:

Когда мы говоримif (w is in S)тогда не является ли эта операция сложностью O (N) или, по крайней мере, O (logN), поскольку элементы должны быть упорядочены по их индексам? Мы должны будем выполнить это для каждого нового узла, доступного из корневого узла, поэтому общая сложность отсутствуетO(NlogN), Кроме того, S являетсястек так что концептуально должен быть доступен только верхний элемент, как мы реализуем поиск в нем? Разве бинарное дерево поиска не должно быть лучшей структурой данных здесь?

В этой части:

иначе, если (W в S), то
v.lowlink: = min (v.lowlink, w.index)

Есть ли конкретная причина для использованияw.index и неw.lowlink? Преимущество использованияw.lowlink было бы, что это ответило бы на предыдущий вопрос (связанный вопрос).LLs для всех узлов в SCC гарантированно будет одинаковым для всех узлов.