2015年5月5日火曜日

HackerRank : clique

問題

ノード数がNでエッジ数がMのグラフの中で最大クリークの最初サイズを求める問題。
https://www.hackerrank.com/challenges/clique

解法

Turán's theoremというのを使えば、ノード数Nでクリークサイズr+1となるようなグラフのエッジ数の最大値は

で求められるので二分探索。
このようなグラフをTuránグラフと言うらしい。完全r部グラフの形をしている。


0 件のコメント:

コメントを投稿