c++随机生成树

用途

主要在对拍时使用，如果造数据需要特殊构造

方法一：并查集

生成树的深度为 \(\sqrt{n}\)

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,fa[100015];
int zhao(int xx){
    if(fa[xx]==xx) return xx;
    else return zhao(fa[xx]);
}
int main(){
    freopen("/dev/urandom","r",stdin);
    srand(getchar()*getchar()*getchar()*time(0));
    int n=rand()%10+2;
    printf("%d\n",n);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    while(cnt<n-1){
        int x=rand()%n+1,y=rand()%n+1;
        int x1=zhao(x),y1=zhao(y);
        if(x1!=y1){
            fa[x1]=y1,cnt++;
            printf("%d %d\n",x,y);
        }
    }
    return 0;
}

方法二：向编号比其小的点连边

生成树的深度为 \(log(n)\)

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    freopen("/dev/urandom","r",stdin);
    srand(getchar()*getchar()*getchar()*time(0));
    int n=rand()%10+2;
    printf("%d\n",n);
    for(int i=2;i<=n;i++){
        printf("%d %d\n",i,rand()%(i-1)+1);
    }
    return 0;
}