tarjan.js

'use strict'

const tags = {
  '1': ['2'],
  '2': ['1', '5'],
  '3': ['4'],
  '4': ['3', '5'],
  '5': ['6'],
  '6': ['7'],
  '7': ['8'],
  '8': ['6', '9'],
  '9': []
}

/*const tags = {
  'pl': ['java'],
  'java': ['code'],
  'code': []
}*/

let components = []

let index = 0
let S = []

let indices = {}
let lowLinks = {}
let onStacks = {}

for (let v in tags) {
  if (typeof indices[v] === 'undefined') {
    strongConnect(v)
  }
}

function strongConnect(v) {
  indices[v] = index
  lowLinks[v] = index
  onStacks[v] = true
  index = index + 1
  S.push(v)

  tags[v].forEach((w) => {
    if (typeof indices[w] === 'undefined') {
      strongConnect(w)
      lowLinks[v] = Math.min(lowLinks[v], lowLinks[w])
    } else if (onStacks[w]) {
      lowLinks[v] = Math.min(lowLinks[v], indices[w])
    }
  })

  if (lowLinks[v] === indices[v]) {
    let component = []
    let w
    while (w != v) {
      w = S.pop()
      onStacks[w] = false
      component.push(w)
    }

    console.log(w, S)

    components.push(component)
  }
}

console.log(components)