(资料图片仅供参考)

我们日常用的随机函数为 rand()，虽然比较慢，但已经足够用了，它会随机生成一个范围在 \([0, 2^{31} - 1]\) 中的一个数。

使用时要用随机种子 seed，可以使用 srand(seed)来设置、更改随机种子，当然，不初始化也是可以的，只是同一个程序用相同的 seed、相同的机器、相同的编译器下，随机的结果将会是一样的。

mt19937是一个随机数生成器类，效用同rand()，随机数的范围同unsigned int类型的取值范围。

其优点是随机数质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于rand()），且速度比rand()快很多。

const int N = 1e5 + 1;int n;struct union_find_set {    int fa[N], siz[N];    int &operator [] (const int& x) {        return fa[x];    }    void reset() {        for (int i = 1; i <= n; ++ i) {            fa[i] = i;            siz[i] = 1;        }    }    int find(int x) {        return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);    }    void Union(int x, int y) {        int fx = find(x), fy = find(y);        if (siz[fx] <= siz[fy]) {            swap(fx, fy);        }        fa[fy] = fx;        siz[fx] += siz[fy];    }} ufs;int main() {    srand(time(0));    n = rand() % 10 + 1;    cout << n << "\n"; // 有多少个点    int cnt = 0;    ufs.reset(); // 并查集初始化    while (cnt != n - 1) {        int x = rand() % n + 1, y = rand() % n + 1;        if (ufs.find(x) != ufs.find(y)) {            cout << x << " " << y << "\n"; // 边            ufs.Union(x, y); // 并查集合并            ++ cnt;        }    }    return 0;}

int main() {    srand(time(0));    int n = rand() % 10 + 1;    cout << n << "\n"; // 有多少个点    for (int i = 2; i <= n; ++ i) {        int x = rand() % (i - 1) + 1;        cout << x << " " << i << "\n";    }    return 0;}

pair e[N << 2];map, bool> mp;int main() {    mt19937 rnd(time(0));    int n = rnd() % 20 + 2;    int m = (n + rnd() % n + 1);    cout << n << " " << m << "\n"; // 有多少个点和边    int cnt = 0;    for (int i = 2; i <= n; ++ i) { // 先构造一棵树        int x = rnd() % (i - 1) + 1;        ++ cnt;        e[cnt] = {x, i};        mp[{x, i}] = 1;    }    for (int i = n; i <= m; ++ i) { // 再随机剩下的边        int x, y;        do {            x = rnd() % n + 1, y = rnd() % n + 1;        } while (x == y || mp[{x, y}]); // 判重        e[++ cnt] = {x, y};        mp[{x, y}] = 1;    }    random_shuffle(e + 1, e + m + 1); // 打乱顺序    for(int i = 1; i <= m; ++i)    cout << e[i].first << " " << e[i].second << "\n";    return 0;}

int l = rand() % n + 1, r = rand() % n + 1;if (l > r)  swap(l, r);cout << l << " " << r << "\n";

关键词：