c++ - 该程序的有效算法

Question

我必须执行从用户那里获取的程序：
n - 元素数
m - 对数（两个元素成对）
然后用户将写入所有对 > 1 和 2；1 和 3, ...
并且应该输出具有最多元素的数字 >> 其中每个元素都与该数字的所有其他元素成对出现。
例如：

---

输入：（第一行 n 和 m）下一行有对

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

输出：1 2 3或4 1 2
（1 2 3 4不好，因为元素 3 和 4 不是成对的）（1 5 也不好，因为 1 5 成对但它们不是最大的）

---

我需要让这个程序在 n = 100000 和 m 高达 300000 的情况下在 2 秒内运行。有什么有效的方法吗？我试过用所有组合来做，然后我检查了所有元素是否成对，但这不是有效的方法（100 年才能做到这一点

Answer 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);
}