仙人掌生成器

背景

网上找不到正确生成仙人掌的 gen，唯一的一篇似乎是错误的，所以手写一篇。
仙人掌的定义

仙人掌：任意一条边最多出现在一个简单环中的无向连通图。
生成算法

给定 \(n\) 作为仙人掌结点数。先随机生成一棵树，作为目标仙人掌的一棵 dfs 树，这保证了图连通这一条件，接下来要做的就是不断往这棵树上加非树边，同时满足「任意一条边最多出现在一个简单环中」这一限制条件。可选地，我们可以限制边数上界。
考虑 dfs 这棵树，当前在 \(u\)，尝试添加一条以 \(u\) 为上端点的非树边，那么下端点 \(v\) 需要满足：\(u\rightarrow v\) 路径上的树边均未被环包含。于是我们可以在 dfs 的时候 return 出一个 \(v\)，作为未来可能作为下端点的点。
\(u\) 的初始返回值就是其本身。考虑 dfs 完 \(u\) 的一个孩子 \(v\)，返回值为 \(t\)，我们有一定概率用 \(t\) 替换 \(u\) 的返回值，如果不作为范围值，有一定概率尝试将 \(u,t\) 之间加一条非树边。
另外，我们可以在此基础上进行适当扩展，例如，要求环必须全都是奇环，要求不能有重边。注意，在允许重边的前提下，重边的个数不能超过 \(2\) 条。
算法分析

该算法的时间复杂度为：\(\mathcal{O}(n+m)\)。
虽然该算法不能保证等概率地，在所有 \(n\) 个结点的仙人掌中，随机选择一棵仙人掌，但是作为对拍的 gen 已经足够了。
代码实现

使用 C++ 实现，请使用 C++14 及以上版本编译。
支持修改随机数种子（默认为当前时间戳）、是否允许重边、是否只允许奇环、点数、边数上界（默认为 \(-1\) 即不限制）。
将生成的仙人掌输出到标准输出流，额外的信息、错误信息输出到标准错误流。程序返回值为 \(0\) 表示生成成功。
输出格式：第一行两个以空格分隔的整数 \(n,m\)，分别表示仙人掌的结点数、边数；接下来 \(m\) 行表示仙人掌的边。

1. #include <cstdio>
2. #include <iostream>
3. #include <vector>
4. #include <random>
5. #include <chrono>
6. using namespace std;
8. /* =========== Parameter =========== */
10. const int SEED = chrono::system_clock::now().time_since_epoch().count();
12. bool multiedge = false;
13. bool onlyOddCircle = false;
15. int n = 1000000;
16. int m_limit = -1;  // -1 for not limit
18. /* =========== Parameter =========== */
20. void _err(const char* msg, int lineNum) {
21.     fprintf(stderr, "Error at line #%d: %s\n", lineNum, msg);
22.     exit(1);
23. }
24. #define err(msg) _err(msg, __LINE__)
26. inline int rand(int l, int r) {
27.     static mt19937 rnd(SEED);
28.     if (l > r) err("invalid range");
29.     return l + rnd() % (r - l + 1);
30. }
32. vector<pair<int, int>> edges;
33. vector<vector<int>> son(n, vector<int>());
34. vector<int> dpt(n);
36. int dfs(int u) {
37.     int res = u;
38.     for (size_t i = 0; i < son[u].size(); ++i) {
39.         int v = son[u][i];
40.                 dpt[v] = dpt[u] + 1;
41.         int t = dfs(v);
42.         if (rand(0, son[u].size()) == 0)
43.             res = t;
44.         else if ((t != v || multiedge)
45.                 && ((dpt[t] - dpt[u] + 1) % 2 == 1 || !onlyOddCircle)
46.                 && (m_limit == -1 || (int)edges.size() < m_limit))
47.             edges.emplace_back(u, t);
48.     }
49.     return res;
50. }
52. signed main() {
53.     // freopen("yzh", "w", stdout);
54.    
55.     if (n < 1) err("n shouldn't be less than 1");
56.     if (m_limit != -1 && m_limit < n - 1)
57.         err("m_limit shouldn't less than n-1");
58.    
59.     for (int i = 1; i < n; ++i) {
60.         int fa = rand(0, i - 1);
61.         edges.emplace_back(fa, i);
62.         son[fa].emplace_back(i);
63.     }
64.     dfs(0);
65.    
66.     for (size_t i = 1; i < edges.size(); ++i)
67.         swap(edges[i], edges[rand(0, i)]);
68.    
69.     printf("%d %d\n", n, (int)edges.size());
70.     for (size_t i = 0; i < edges.size(); ++i) {
71.         int u = edges[i].first;
72.         int v = edges[i].second;
73.         if (rand(0, 1)) swap(u, v);
74.         printf("%d %d\n", u + 1, v + 1);
75.     }
76.    
77.     fprintf(stderr, "Success!\n");
78.     fprintf(stderr, "n = %d, m = %d\n", n, (int)edges.size());
79.     fprintf(stderr, "circle = %d\n", (int)edges.size() - (n - 1));
80.     return 0;
81. }

复制代码

一些扩展

随机生成的仙人掌环特别小，作为对拍来说够用了。如果是造数据，希望生成一个大一点的环，提前类似基环树的方式，在根部放一个大环，对环上每一个节点应用仙人掌生成算法，即可。
Checker

写了一个程序用来验证 gen 的正确性。使用并查集判断连通性、dfs 序求 \(\operatorname{lca}\)、差分完成树链覆盖。时间复杂度是 \(\mathcal{O}(m+n\log n)\) 的，尽管可以优化到线性 \(\mathcal{O}(n+m)\)。
支持修改是否检查仅允许奇环。
从标准输入流读入图，程序返回值为 \(0\) 表示图为仙人掌。
[code]#include #include #include using namespace std;/* =========== Parameter =========== */bool checkOnlyOddCircle = false;const int N = 1e6 + 10;/* =========== Parameter =========== */void _err(const char* msg, int lineNum) {    fprintf(stderr, "Error at line #%d: %s\n", lineNum, msg);    exit(1);}#define err(msg) _err(msg, __LINE__)const int lgN = __lg(N) + 1;int n, m;namespace $dsu {int fa[N];int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }}vector son[N];vector edges;int fa[N], dpt[N];int st[lgN][N], idx[N], timer;void dfs(int u) {    st[0][idx = ++timer] = u;    for (int v : son) {        if (v == fa) continue;        fa[v] = u, dpt[v] = dpt + 1;        dfs(v);    }}inline int Min(int u, int v) {    return dpt < dpt[v] ? u : v;}inline int lca(int u, int v) {    if (u == v) return u;    if ((u = idx) > (v = idx[v]))        swap(u, v);    int p = __lg(v - u++);    return fa[Min(st[p], st[p][v - (1 = 2) err("an edge appears in more than one simple circle");}signed main() {    scanf("%d%d", &n, &m);    if (n < 1) err("n shouldn't be less than 1");    if (n > 1000000) err("n is too big that input can't be determined");    for (int i = 1; i  n) err("node number out of range");        int tu = $dsu::get(u), tv = $dsu::get(v);        if (tu == tv) {            edges.emplace_back(u, v);        } else {            $dsu::fa[tu] = tv;            son.emplace_back(v);            son[v].emplace_back(u);        }    }    for (int i = 2; i