一、随机生成一个小于等于$n$的数
int RAND(int n) {
srand((int)time(0));
return rand()%n+1;
}
二、随机生成排列
int t[MAXN];
int mp(int n) {
int i;
srand((int)time(0));
for(int i = 1; i <= n; ++i) t[i] = i;
random_shuffle(t + 1, t + 1 + n);//STL的打乱数组函数
}
三、随机生成树
1、以1为根的树
int mt1(int n) {
int i;
srand((int)time(0));
for (int i = 2; i <= n; ++i) printf("%d %d\n", i, RAND(i - 1));
}
2、以任意结点为根的树
int mt2(int n) {
int i;
srand((int)time(0));
mp(n);
for (int i = 2; i <= n; ++i) printf("%d %d\n", t[i], t[RAND(i - 1)]);
}
四、随机生成图
1、连通图
先构造一棵树，再随意加边
2、普通图
随便加边就可以了
3、无重边
用set记录二元组
4、无自环
起点终点不一致即可
5、DAG
随机一个排列作为拓扑序，然后随机从前面的点加边到后面
6、无大环套小环
每个点至多一个出度
