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

Question

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

---

INPUT: (first row n and m) next rows there pairs

                                 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 成对但不是最大的)

---

我需要让这个程序在 2 秒内运行，n = 100000，m 高达 300000 有什么有效的方法吗？我试着用所有组合来做，然后我检查了所有元素是否成对，但这不是有效的方法(100 年来这样做

Answer 1

如果我对您的问题的理解正确，您可以保留一个包含 10 个元素 (0-9) 的数组，然后为每个元素保留另一个 bool 值数组，以确定是否观察到一对:

bool pairs[10][10];

当您看到 (1,2) 对时，您可以:

pairs[1][2] = true;

要找出哪个数字的对数最多，您只需对 bool 值求和即可。

但是，您确实有一个问题，您希望 (1, 2) 与 (2, 1) 相同。为了解决这个问题，你可以强加一个命令:

void order(int &a, int &b) {
    if (b < a) swap(a, b);
}