問題 連結無向グラフのカットのうち最小のものを求める。 実装 ソースコード(IdeOne) 解説 乱択アルゴリズムによる実装。 一辺をランダムに選んで縮約していく。 最後に2点残る。これらの点に縮約された点が大域最小カットである可能性は以上。 頂点の数をと…