|
|
# Queue
class Array
alias_method :enqueue, :push
alias_method :dequeue, :shift
end
# u : Index of nodes starting from 1...N
# k : degree of this node
# v : array of vertices connected with this node
# c : :white(=undiscovered), :gray(=frontier), :black(finished searching)
# d : distance when the vertex is first discovered
# pi: predecessor vertex
Node = Struct.new(:u, :k, :v, :c, :d, :pi)
class Graph
attr :nodes, true
def initialize(n)
@nodes = Array.new(n){ Node.new }
end
def add_graph_node(u, v, d = 0)
@nodes[u-1].u = u
if not v.nil?
(@nodes[u-1].v ||= []).push(v)
@nodes[u-1].k = @nodes[u-1].v.length ||= 0
else
@nodes[u-1].v = [] if @nodes[u-1].v.nil?
@nodes[u-1].k = 0
end
@nodes[u-1].c = :white
@nodes[u-1].d = d
@nodes[u-1].pi = nil
end
def reset()
@nodes.each do |node|
node.c = :white
node.d = -1
node.pi = nil
end
end
def dist()
puts "d : #{@nodes.map{|node| node.d}.to_a.to_s}"
puts "pi: #{@nodes.map{|node| node.pi}.to_a.to_s}"
end
def bfs(start, queue)
start_idx = (start - 1).to_i
@nodes[start_idx].c = :gray
@nodes[start_idx].d = 0
@nodes[start_idx].pi = nil
queue.enqueue(@nodes[start_idx])
while not queue.empty?
u = queue.dequeue
break if u.v.nil?
u.v.each do |label|
v = @nodes[label-1]
if v.c == :white
v.c = :gray
v.d = u.d.to_i + 1
v.pi = u
queue.enqueue(v)
end
end
u.c = :black
end
end
end
# start
lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
graph = Graph.new(N)
for i in 1...N+1
seps = array[i].split(" ")
u = seps.drop(0)[0].to_i
k = seps.drop(1)[0].to_i
vs = seps.drop(2).map(&:to_i)
#puts "add_graph_node(#{u} <--> #{v})"
for v in vs
graph.add_graph_node(u, v)
end
graph.add_graph_node(u, nil) if vs.length == 0
end
graph.bfs(1, [])
graph.nodes.each_with_index do |elem, idx|
puts "#{idx+1} #{graph.nodes[idx].d.to_i}"
end
|