background
The gen that correctly generated the cactus was not found online, and the only article seemed to be wrong, so I wrote one by hand.
The definition of cactus
Cactus: An undirected connection diagram in which any edge appears at most in a simple ring.
Generate algorithm
Given\(n\)As the number of cactus nodes. First, a tree is randomly generated as a dfs tree for the target cactus, which ensures the condition of connecting the graph. The next thing to do is to continuously add non-tree edges to this tree, while meeting the restriction condition of "any edge appears at most in a simple ring". Optionally, we can limit the upper bound of edges.
Consider dfs, the tree is currently\(u\), try adding one to\(u\)It is the non-tree edge of the upper endpoint, then the lower endpoint\(v\)Need to meet:\(u\rightarrow v\)No tree edges on the path are included by rings. So we can do it in dfsreturnOut one\(v\), as a point that may be used as the lower end point in the future.
\(u\)The initial return value of . Consider dfs\(u\)A child\(v\), the return value is\(t\), we have a certain probability of using\(t\)replace\(u\)If the return value is not used as the range value, there is a certain probability that the\(u,t\)Add a non-tree edge between them.
In addition, we can make appropriate expansion on this basis. For example, it is required that the rings must be all odd rings and that there must be no heavy edges. Note that the number of heavy edges cannot exceed the number of heavy edges when allowed.\(2\)strip.
Algorithm Analysis
The time complexity of this algorithm is:\(\mathcal{O}(n+m)\)。
Although the algorithm cannot guarantee equal probability,\(n\)Among the cactus at one node, a random cactus is selected, but it is enough for gen to be used as a match.
Code implementation
Use C++ implementation, please use C++14 and above to compile.
Supports modifying random number seeds (default is the current timestamp), whether to allow heavy edges, whether only odd rings, points, and upper bounds of edges (default is\(-1\)That is, no restrictions).
The generated cactus is output to the standard output stream, and additional information and error information are output to the standard error stream. The program returns the value\(0\)Indicates that the generation is successful.
Output format: Two space-separated integers on the first line\(n,m\), respectively represent the number of nodes and edges of the cactus; next\(m\)The line indicates the edge of the cactus.
#include <cstdio>
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
/* =========== Parameter =========== */
const int SEED = chrono::system_clock::now().time_since_epoch().count();
bool multiedge = false;
bool onlyOddCircle = false;
int n = 1000000;
int m_limit = -1; // -1 for not limit
/* =========== 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__)
inline int rand(int l, int r) {
static mt19937 rnd(SEED);
if (l > r) err("invalid range");
return l + rnd() % (r - l + 1);
}
vector<pair<int, int>> edges;
vector<vector<int>> son(n, vector<int>());
vector<int> dpt(n);
int dfs(int u) {
int res = u;
int cnt = 0;
for (size_t i = 0; i < son[u].size(); ++i) {
int v = son[u][i];
dpt[v] = dpt[u] + 1;
int t = dfs(v);
if (rand(0, son[u].size()) == 0)
res = t;
else if ((t != v || (multiedge && cnt < 2))
&& ((dpt[t] - dpt[u] + 1) % 2 == 1 || !onlyOddCircle)
&& (m_limit == -1 || (int)() < m_limit))
edges.emplace_back(u, t), cnt += t == v;
}
return res;
}
signed main() {
// freopen("yzh", "w", stdout);
if (n < 1) err("n shouldn't be less than 1");
if (m_limit != -1 && m_limit < n - 1)
err("m_limit shouldn't less than n-1");
for (int i = 1; i < n; ++i) {
int fa = rand(0, i - 1);
edges.emplace_back(fa, i);
son[fa].emplace_back(i);
}
dfs(0);
for (size_t i = 1; i < (); ++i)
swap(edges[i], edges[rand(0, i)]);
printf("%d %d\n", n, (int)());
for (size_t i = 0; i < (); ++i) {
int u = edges[i].first;
int v = edges[i].second;
if (rand(0, 1)) swap(u, v);
printf("%d %d\n", u + 1, v + 1);
}
fprintf(stderr, "Success!\n");
fprintf(stderr, "n = %d, m = %d\n", n, (int)());
fprintf(stderr, "circle = %d\n", (int)() - (n - 1));
return 0;
}
Checker
A program was written to verify the correctness of gen. Use and search set to determine connectivity, dfs order\(\operatorname{lca}\), differential completion of tree chain coverage. Time complexity is\(\mathcal{O}(m+n\log n)\)Although it can be optimized to linear\(\mathcal{O}(n+m)\)。
Supports modification to check whether to allow only odd rings.
Read the graph from the standard input stream, and the program returns the value\(0\)The picture shows a cactus.
#include <cstdio>
#include <iostream>
#include <vector>
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<int> son[N];
vector<pair<int, int>> edges;
int fa[N], dpt[N];
int st[lgN][N], idx[N], timer;
void dfs(int u) {
st[0][idx[u] = ++timer] = u;
for (int v : son[u]) {
if (v == fa[u]) continue;
fa[v] = u, dpt[v] = dpt[u] + 1;
dfs(v);
}
}
inline int Min(int u, int v) {
return dpt[u] < dpt[v] ? u : v;
}
inline int lca(int u, int v) {
if (u == v) return u;
if ((u = idx[u]) > (v = idx[v]))
swap(u, v);
int p = __lg(v - u++);
return fa[Min(st[p][u], st[p][v - (1 << p) + 1])];
}
int sum[N];
void redfs(int u) {
for (int v : son[u]) {
if (v == fa[u]) continue;
redfs(v);
sum[u] += sum[v];
}
if (sum[u] > 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; ++i) $dsu::fa[i] = i;
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
if (u == v) err("self-loop exists");
if (u < 1 || u > n) err("node number out of range");
if (v < 1 || v > 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[u].emplace_back(v);
son[v].emplace_back(u);
}
}
for (int i = 2; i <= n; ++i)
if ($dsu::get(i) != $dsu::get(1))
err("graph not connected");
dfs(1);
for (int k = 1; k < lgN; ++k)
for (int i = 1; i + (1 << k) - 1 <= n; ++i)
st[k][i] = Min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
for (size_t i = 0; i < (); ++i) {
int u = edges[i].first;
int v = edges[i].second;
int p = lca(u, v);
++sum[u], ++sum[v];
sum[p] -= 2;
int len = dpt[u] + dpt[v] - 2 * dpt[p] + 1;
if (len % 2 == 0 && checkOnlyOddCircle)
err("odd circle exists");
}
redfs(1);
fprintf(stderr, "Success!\n");
fprintf(stderr, "the input is a cactus with %d circle(s)!\n", (int)());
return 0;
}
advertise
My blog post"Learning Notes on the Round Square Tree - A Way of Thinking on the Connecting Components of Double Points"It took a month and a half to be written and will be released soon. Welcome to learn!