$1167C$ — 新闻传播

读完题目后的第一个想法是用图论的术语重新表述问题。把人视为顶点，若两个人 $x$ 和 $y$ 属于同一个群组，则在 $x$ 和 $y$ 之间连一条边。实际上，如果第 $x$ 个人开始传播新闻，那么他所在连通分量中的每个人都会收到新闻。因此，任务就是计算每个顶点所在连通分量的大小。

到目前为止，图的边数可能达到 $O(n^2)$（比如所有人都在同一个群组的情况）。我们需要在不改变连通分量的前提下减少边数。对于每个群组，我们知道组内的人一定属于同一个连通分量。我们不必在组内每对顶点之间都连边，而只需在组内相邻的每对顶点之间连边（例如按输入顺序相邻）。容易看出，他们仍然在同一个连通分量中。

这样构建出来的图边数为 $O(\sum_{i=1}^{m} k_i)$，这个数值要小得多。我们可以使用 DFS 或并查集来寻找连通分量并计算其大小。

总时间复杂度：$O(n + \sum_{i=1}^{m} k_i)$。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
    // 用法: ./gen n m [seed]
    // 生成 m 个群组，每个群组大小随机，总大小限制在 5e5 以内
    int n = 500000, m = 5000;
    unsigned seed = random_device{}();
    if (argc >= 3) {
        n = atoi(argv[1]);
        m = atoi(argv[2]);
    }
    if (argc >= 4) {
        seed = atoi(argv[3]);
    }
    mt19937 rng(seed);
    uniform_int_distribution<int> grp_size(0, n / m + 10); // 平均大小约 n/m

    int total = 0;
    vector<int> users(n);
    iota(users.begin(), users.end(), 1);
    shuffle(users.begin(), users.end(), rng);

    cout << n << ' ' << m << '\n';
    int idx = 0;
    for (int i = 0; i < m; ++i) {
        int k = grp_size(rng);
        if (total + k > 500000) k = 500000 - total;
        cout << k;
        for (int j = 0; j < k; ++j) {
            cout << ' ' << users[idx++];
            if (idx >= n) idx = 0; // 循环使用用户编号
        }
        total += k;
        cout << '\n';
        if (total >= 500000) break;
    }
    return 0;
}