随机数生成与样例构造
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int r(int a, int b) {return rnd() % (b - a + 1) + a;
}void graph(int n, int root = -1, int m = -1) {vector<pair<int, int>> t;for (int i = 1; i < n; i++) { // 先建立一棵以0为根节点的树t.emplace_back(i, r(0, i - 1));}vector<pair<int, int>> edge;set<pair<int, int>> uni;if (root == -1) root = r(0, n - 1); // 确定根节点for (auto [x, y] : t) { // 偏移建树x = (x + root) % n + 1;y = (y + root) % n + 1;edge.emplace_back(x, y);uni.emplace(x, y);}if (m != -1) { // 如果是图，则在树的基础上继续加边for (int i = n; i <= m; i++) {while (true) {int x = r(1, n), y = r(1, n);if (x == y) continue; // 拒绝自环if (uni.count({x, y})) continue; // 拒绝重边edge.emplace_back(x, y);uni.emplace(x, y);}}}random_shuffle(edge.begin(), edge.end()); // 打乱节点for (auto [x, y] : edge) {cout << x << " " << y << endl;}
}