class AcLibraryRb::SCC

Strongly Connected Components

Public Class Methods

new(n) click to toggle source

initialize graph with n vertices

# File lib_lock/ac-library-rb/scc.rb, line 5
def initialize(n)
  @n = n
  @edges = []
end

Public Instance Methods

add(x, to = nil) click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 26
def add(x, to = nil)
  to ? add_edge(x, to) : add_edges(x)
end
add_edge(from, to) click to toggle source

add directed edge

# File lib_lock/ac-library-rb/scc.rb, line 11
def add_edge(from, to)
  unless 0 <= from && from < @n and 0 <= to && to < @n
    msg = "Wrong params: from=#{from} and to=#{to} must be in 0...#{@n}"
    raise ArgumentError.new(msg)
  end

  @edges << [from, to]
  self
end
add_edges(edges) click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 21
def add_edges(edges)
  edges.each{ |from, to| add_edge(from, to) }
  self
end
scc() click to toggle source

returns list of strongly connected components the components are sorted in topological order O(@n + @edges.size)

# File lib_lock/ac-library-rb/scc.rb, line 33
def scc
  group_num, ids = scc_ids
  groups = Array.new(group_num) { [] }
  ids.each_with_index { |id, i| groups[id] << i }
  groups
end

Private Instance Methods

csr() click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 74
def csr
  start = [0] * (@n + 1)
  elist = [nil] * @edges.size
  @edges.each { |(i, _)| start[i + 1] += 1 }
  @n.times { |i| start[i + 1] += start[i] }
  counter = start.dup
  @edges.each do |(i, j)|
    elist[counter[i]] = j
    counter[i] += 1
  end
  [start, elist]
end
scc_ids() click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 42
def scc_ids
  start, elist = csr
  now_ord = group_num = 0
  visited, low, ord, ids = [], [], [-1] * @n, []
  dfs = ->(v) {
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited << v
    (start[v]...start[v + 1]).each do |i|
      to = elist[i]
      low[v] = if ord[to] == -1
                 dfs.(to)
                 [low[v], low[to]].min
               else
                 [low[v], ord[to]].min
               end
    end
    if low[v] == ord[v]
      loop do
        u = visited.pop
        ord[u] = @n
        ids[u] = group_num
        break if u == v
      end
      group_num += 1
    end
  }
  @n.times { |i| dfs.(i) if ord[i] == -1 }
  ids = ids.map { |x| group_num - 1 - x }
  [group_num, ids]
end