入力を取っています、例えば 4 1 3 1 2 2 4
最初の行はノードの数で、その後の行はエッジです。グラフに色を付けようとする必要があります。できない場合は、エラーの原因となっているグラフ内のサイクルをリストする必要があります。
グラフの 1 つに 1,000,000 ノードが含まれていることを除いて、これはこれまでのところ問題ありません。それを使用しようとするたびに、スタック オーバーフロー エラーが発生します。さらに合理化し、Eclipse の最大ヒープ サイズを 1024m に上げたにもかかわらずです。
私はコードを求めているのではなく、エラーが発生し続けるために露骨に間違ったことをしているかどうかを尋ねているだけです。
2 部グラフの場合は、いつでも 2 色だけで色を付けることができます (たとえば、最初のパーティションを白に、2 番目のパーティションを黒にします)。
通常、グラフに色を付ける場合、色の数を指定する必要があります。各ノードに異なる色を割り当てることで、いつでもグラフに色を付けることができます。別の例: 平面グラフの場合、4 色のみが必要です。ただし、ほとんどのグラフでは、グラフの [色数] は [NP] です。
[NP] http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems
おそらく、サイクル検出アルゴリズムを最適化できます。これはあなたを助けるかもしれません: http://en.wikipedia.org/wiki/Cycle_detection
それ以外では、100 万のノードと隣接行列を一度に処理するには多すぎる可能性があるため、一度にグラフの一部だけを読み込む方法があるかもしれません。
まあ、これはNP完全問題 (最長サイクル) なので、この種のことが起こる可能性があります。
おそらく、ヒープをもう一度バンプして、実行させます...
編集：気にしないでください。削減を後方に取得しました。