アレイがグラフを形成できるかどうかを調べる

Question

[インタビュー質問]最近のオンラインインタビューでこの質問を受けました。私はそれを解決する方法を知りませんでした。誰でも私がJavaで学ぶことができるようにこれを解決するのを助けてくれますか？

トムは問題解決に非常に優れています。トムのスキルをテストするために、ジェリーはトムにグラフの問題を尋ねます。 Jerryは、N個の整数の配列AをTomに返します。

グラフは、自己ループもマルチエッジもない場合、簡単なグラフです。

今、JerryはN個の頂点の簡単なグラフを設計できるかどうかをTomに尋ねる。条件は、TomがAの各要素をグラフの頂点の度数に対して1回だけ使用しなければならないことです。

今、トムはあなたの助けが彼のグラフをデザインすることを望んでいます。グラフが設計可能な場合は「YES」を、それ以外の場合は「NO」（引用符なし）を印刷します。

入力 テストケースの数を示す1行目の1つの整数Tです。 テストケースごとに2行あります。 最初の行が二行目は、各テストケースについてA.

出力 、プリント「YES」の要素を表す、N-空間分離整数を有する配列A の要素の数を表す、単一の整数Nであります新しい行でグラフを設計できるかどうかを "NO"（引用符なし）にします。

制約

1<= T <= 100 
1<= N <= 100 
0<= Element of A <= 5000 

サンプルテストケース

入力

1 
2 
1 1 

出力

YES 

このテストケースについて説明 、 2つの頂点を持つ単純なグラフは、各頂点が最初のテストケースについて度1

入力

2 
3 
1 2 1 
3 
1 1 1 

出力

YES 
NO 

説明 を有する場合、我々は簡単に設計することができ、設計することができます[1、2、1]として次数系列を持つ3頂点のグラフ。最初の頂点の次数は1であり、2番目の頂点は2であり、3番目の頂点は1です。 2番目のテストケースでは、次数系列が[1,1,1]の3つの頂点の簡単なグラフを作成できません。

Answer 1

必要条件の1つは、Aの要素の合計が偶数であることです。これは、各エッジ が隣接リスト内で2回カウントされるためです。

次に、グラフの作成を試みるか、少なくともノードのペアを「割り当て」ます。リストが構成されているため、その後の工程で選別、マージソート工程でO（N）で行うことができることを

Sort elements of A in decending order, 
Let the largest (first) element be a, 
Check are element on positions 2 to a+1 larger than 0, 
    If there is a element with value 0 than it is not possible to construct a graph, 
Decrease these a elements by 1 and set first element to 0, 
Repeat process until all elements are 0. 

注3ソート部の ：

• 最初の要素（0）に行くことができます最後、
• 要素でソートされた部分、
• 残りもソートされています。