🌳
[ABC287 C] Path Graph?
パスグラフか判定する問題。
前提知識
次数とは？
節から出ている辺の数のこと。
パスグラフとは？
- 無駄がない (閉路がない)
- 辺の数 = 節の数 - 1
- 次数がすべて 2 以下
- 上のグラフで言えば A=1 B=2 C=1 なので正しい
- 連結している
- 森の中に木の数が1つ
コード (AC)
N, M = gets.split.collect(&:to_i) # => [4, 3]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 3], [4, 2], [3, 2]]
ds = DisjointSet.new(1..N).unites(XY)
valid = [
M = N - 1,
XY.flatten.tally.all? { |_, c| c <= 2 },
ds.tree_count == 1,
].all?
valid # => true
puts valid ? "Yes" : "No"
DisjointSet クラスで判定を吸収する
SOLID の S こと単一責任の原則から言えば賛否ありそうだが、入力する辺をすべて保持しておけば内部で判定が行えて便利ではある。
DisjointSet.prepend Module.new {
def initialize(...)
@edges = []
super
end
def unite(x, y)
@edges << [x, y]
super
end
def path_graph?
v = true
v &&= @edges.size == @parents.size.pred
v &&= @edges.flatten.tally.all? { |_, c| c <= 2 }
v &&= tree_count == 1
end
}
N, M = gets.split.collect(&:to_i) # => [4, 3]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 3], [4, 2], [3, 2]]
ans = DisjointSet.new(1..N).unites(XY).path_graph? # => true
puts ans ? "Yes" : "No"
Discussion