2

ユーザーから取得するプログラムを実行する必要があります:
n - 要素
の数 m - ペアの数 (2 つの要素がペアになっている)
、ユーザーはすべてのペア > 1 と 2 を書き込みます。1 と 3、...
そして、最も多くの要素を持つ番号が出力されます >> ここで、すべての要素はその番号の他のすべての要素とペアになっています。
例えば：

入力: (最初の行 n と m) 次の行にはペアがあります

                                 5 6           
                                 1 2
                                 1 3
                                 1 4
                                 1 5
                                 3 2
                                 4 2

OUTPUT:1 2 3または4 1 2
(1 2 3 4要素 3 と 4 がペアになっていないので良くありません) (1 5 もペアになっているが最大ではないので良くありません)

n = 100000 で m が 300000 までの場合、このプログラムを 2 秒以内に動作させる必要があります。それを行う効果的な方法はありますか? 私はすべての組み合わせでそれをやろうとしましたが、すべての要素がペアになっているかどうかを確認しましたが、効果的な方法ではありません(そのようにするのに100年かかります)

4

1 に答える 1

1

問題を正しく理解していれば、10 個の要素 (0 ～ 9) の配列を保持し、要素ごとに、ペアが観察されたかどうかのブール値の別の配列を保持できます。

bool pairs[10][10];

ペア (1,2) が表示されたら、次のようにします。

pairs[1][2] = true;

ペアが最も多い数を特定するには、ブール値を合計するだけです。

ただし、(1, 2) を (2, 1) と同じにしたいという問題があります。それに対処するために、次のような命令を課すことができます。

void order(int &a, int &b) {
    if (b < a) swap(a, b);
}
于 2012-10-12T17:38:51.077 に答える