私は自由時間にプログラミングの問題を解決する練習をしています。私がしばらく前に見つけたこの問題は、まだそれを解決する方法がわかりません：
n個の頂点とm個のエッジ（両方とも2×10 6未満）を持つ特定の無向グラフの場合、頂点をできるだけ多くのグループに分割する必要がありますが、条件は1つです。異なるグループの頂点の各ペアはエッジで接続されています。各頂点は正確に1つのグループにあります。最後に、各グループのサイズを知る必要があります。
このソリューションを思いついたとき、私は誇りに思いました。元のグラフの補グラフを検討し、それに素集合データ構造を使用します。それは私たちに正しい答えを与えます（証明するのは難しくありません）。しかし、それは理論的な解決策にすぎません。与えられた制約があると、それは非常に悪く、最適ではありません。しかし、私はこのアプローチがどういうわけか賢く修正できると信じています。しかし、どのように？
誰か助けてもらえますか？
編集：1から7および16のエッジまでの頂点を持つグラフの場合：
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
サイズが1、2、4の3つのグループがあります。
これらのグループは、それぞれ{4}、{5,7}、{1,2,3,6}です。異なるグループの頂点の各ペアを接続するエッジがあり、これ以上グループを作成することはできません。