#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Tarjan
#

func tarjan (k) {

    var(:onstack, :index, :lowlink, *stack, *connected)

    func strong_connect (vertex, i=0) {

         index{vertex}   = i
         lowlink{vertex} = i+1
         onstack{vertex} = true
         stack << vertex

         for connection in (k{vertex}) {
             if (index{connection} == nil) {
                 strong_connect(connection, i+1)
                 lowlink{vertex} `min!` lowlink{connection}
             }
             elsif (onstack{connection}) {
                 lowlink{vertex} `min!` index{connection}
             }
        }

        if (lowlink{vertex} == index{vertex}) {
            var *node
            do {
                node << stack.pop
                onstack{node.tail} = false
            } while (node.tail != vertex)
            connected << node
        }
    }

    { strong_connect(_) if !index{_} } << k.keys

    return connected
}

var tests = [
    Hash(
         0 => <1>,
         1 => <2>,
         2 => <0>,
         3 => <1 2 4>,
         4 => <3 5>,
         5 => <2 6>,
         6 => <5>,
         7 => <4 6 7>,
    ),
    Hash(
        :Andy => <Bart>,
        :Bart => <Carl>,
        :Carl => <Andy>,
        :Dave => <Bart Carl Earl>,
        :Earl => <Dave Fred>,
        :Fred => <Carl Gary>,
        :Gary => <Fred>,
        :Hank => <Earl Gary Hank>,
    )
]

var results = [
    [["0", "1", "2"], ["3", "4"], ["5", "6"], ["7"]],
    [["Andy", "Bart", "Carl"], ["Dave", "Earl"], ["Fred", "Gary"], ["Hank"]],
]

tests.each {|t|
    var r = tarjan(t).map{.sort}.sort
    assert_eq(r, results.shift)
    say ("Strongly connected components: ", r)
}