gistfile1.txt

# With this algorithm, we merge/contract the head into the tail
# vertex, i.e., copy edges of head vertex into the tail vertex
# and then delete the head vertex.

adj_list = {}
file = File.read('./kargerMinCut.txt');nil
file.each_line do |line|
  line_array = line.strip.split
  vertex = line_array.shift
  adj_list[vertex.to_s] = line_array
end

def randomized_contraction(adjacency_list)
  adj_list         = adjacency_list.dup

  # The contraction hash key is the old vertex and its value is the
  # value of the vertex that it was merged into.
  contraction_hash = {}

  # The deleted hash key is a vertex and its value is an array of vertices
  # that were deleted and merged into the current vertex.
  deleted_hash     = {}

  while adj_list.size > 2
    tail_vertex     = adj_list.keys.sample
    adj_row         = adj_list[tail_vertex]

    head_vertex = adj_row.sample
    # Head vertices may be contracted into tail vertices
    # multiple times. The following while loop will find
    # the last remaining tail vertex in such chains.
    while contraction_hash[head_vertex]
      head_vertex = contraction_hash[head_vertex]
    end

    adj_list[tail_vertex] = adj_list[tail_vertex].concat Array(adj_list[head_vertex])

    adj_list.delete head_vertex
    contraction_hash[head_vertex] = tail_vertex
    if deleted_hash[tail_vertex].nil?
      deleted_hash[tail_vertex] = Array(head_vertex)
    else
      deleted_hash[tail_vertex].concat Array(head_vertex)
    end
    if deleted_hash[head_vertex]
      deleted_hash[tail_vertex].concat deleted_hash[head_vertex]
      deleted_hash.delete head_vertex
    end
    
    adj_list[tail_vertex].delete(tail_vertex)
    deleted_hash[tail_vertex].each do |v|
      adj_list[tail_vertex].delete v
    end
  end

  adj_list[adj_list.keys.first].count
end

file = File.open('./result.txt', 'a')
file.write " #{randomized_contraction(adj_list)} "
file.close