[ABC177 D] Friends
最大の木の大きさを求める問題。
グループとは？
この問題は読解力と柔軟な発想が試される。自分は「同じグループの中に友達がいない」を読んでグループ自体が「友達」を表わすので「同じ友達の中に友達がいない」とはいったいどういう状況なんだ？ となってすぐ詰んだ。
ここでいうグループとは友達関係を作ったあとの話で、友達関係を分断するために、悪意を持って分けたときのグループになる。この「悪意を持って分けたときのグループ」とはなにか？
先生の立場で考える
私は過疎地の小学校でクラス担任をしている。このクラスには生徒 A, B, C, D, E がいる。全員で5人だ。生徒らは人見知りだが友達といるときだけ異常にやかましい。授業中でもやかましいので友達同士で班にしたくない。だからといって5つの班を作って一人一班にするのは何のための班だと言い出すに決まっている。それとなく人見知りを発動するように班を作るにはどうすればいいだろうか？
計画を練る
まず現状の仲良し派閥は ABE CD の2つだ。そこで手始めに CD を解体してみると ABE C D となって少し静かになるものの最大派閥 ABE をどうにかしないといけない。ABE も解体すると A B E C D となって解決か。いや、これでは一人一班になってしまう。友達でないやつ同士で班にしてしまえば静かなことには変わりない。最初に分けた C と D を班長ってことにして A B E を振り分けると CAE DB となって解決か。いや、これは友達同士の A と E が同じ班にいるので失敗だ。最大派閥の方を先に解体してから弱小派閥を振り分けていくのはどうだろう？ A B E のそれぞれを班長にして、弱小派閥の C D を振り分けていくと AC BD E となって人見知りだけの班になる。これだ。これで静かに授業ができる。
問いは？
ここで問題に戻ると問われているのは「何班か？」なので、答えは AC と BD と E の 3 班になる。この 3 は元々どこから来たのか？ 元は A B E の3人である。言い換えると最大派閥の人数である。C と D を振り分ける前にもうわかっている。
したがってこの問題は「最大派閥の人数」こと「いちばん大きな木の大きさ」を求める問題に言い換えることができる。
ヒント
X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です
は、素集合データ構造を示唆している。
ds = DisjointSet.new
ds.unite("X", "Y")
ds.unite("Y", "Z")
ds.same?("X", "Z") # => true
コード (AC)
N, M = gets.split.collect(&:to_i) # => [5, 3]
AB = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [3, 4], [5, 1]]
p DisjointSet[AB].tree_size_max # => 3
Discussion