基本的には前書いた内容。 kousuke.hatenablog.com1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。 動作 0. 頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で…

すこし忘れていたのでメモ rootで親をつなぎかえるのが肝。 class UnionFind < Array def initialize(n) super(n){|i| i} end def root(i) self[i] == i ? i : self[i] = root(self[i]) end def unite(i,j) self[root(i)] = root(j) end def same?(i,j) root…