如何优雅地生成仙人掌图 - liuchanglc

用途

如果某个无向连通图的任意一条边至多只出现在一条简单回路里，我们就称这张图为仙人掌图。

所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

在某些情况下，我们会需要生成仙人掌图来检验代码的正确性。

随机连边的话效率太低，而且生成的图也可能不合法。

看上去似乎不大好实现，但实际上有一种比较优秀的做法：

对于原树进行随机链剖分，随机几个点向链顶连边即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rg register
const int maxn=2e5+5;
int h[maxn],tot=1,x[maxn],y[maxn];
struct asd{
	int to,nxt;
}b[maxn<<1];
void ad(rg int aa,rg int bb){
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	h[aa]=tot++;
}
int tp[maxn];
bool vis[maxn];
void dfs(rg int now,rg int lat){
	rg int jud=0;
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==lat) continue;
		if(!jud) tp[u]=tp[now],jud=1;
		else tp[u]=u;
		dfs(u,now);
	}
}
int main(){
	freopen("/dev/urandom","r",stdin);
	srand(getchar()*getchar()*getchar()*time(0));
	freopen("data.in","w",stdout);
	memset(h,-1,sizeof(h));
	int n=rand()%10+2,m=n-1;
	rg int aa,bb;
	tp[1]=1;
	for(rg int i=2;i<=n;i++){
		aa=rand()%(i-1)+1,bb=i;
		x[i-1]=aa,y[i-1]=bb;
		ad(aa,bb),ad(bb,aa);
	}
	dfs(1,0);
	rg int cnt=rand()%10+1;
	for(rg int i=1;i<=cnt;i++){
		aa=rand()%n+1;
		bb=tp[aa];
		if(aa!=bb && !vis[bb]){
			x[++m]=aa,y[m]=bb;
			vis[bb]=1;
		}
	}
	printf("%d %d\n",n,m);
	for(rg int i=1;i<=m;i++){
		printf("%d %d\n",x[i],y[i]);
	}
	return 0;
}