c++随机生成树

分析

当我们写完一道题，自认为它是正解，但是交上去却WA的时候，我们该怎么办呢

当我们已经想出了一道的暴力解法，又想出了一种比较优秀的解法，但不知道这种解法对错与否，我们该怎么办呢

答案显然是对拍

对于我们之前做过的题，可能对数据的要求并不是那么严格，所以一个rand()%a+b就可以解决问题

但是最近，我们学习了树形DP，很多题目上都要求给出的数据必须是严格的一棵树，这样的话，我们随机生成数据就有了难度

但是，联系我们之前学过的知识，我们可以用并查集解决这个问题

代码

#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(){
    srand(time(0));
    int n=rand()%10+2;
    printf("%d
",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
",x,y);
    }
    }
    return 0;
}