并查集 给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 输入 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 输出 Yes Yes No
按秩合并、路径压缩 //路径压缩 O(α) int fa[N]; void init(int _n) {     rep(i,1,_n + 1)         fa[i] = i; } int find(int x) {     if (x == fa[x]) return x;     return fa[x] = find(fa[x]);     //fa[x] = find[fa[x]] 每次查询树根均记录下来，下次可以直接查询 } void merge(int u, int v) {     int fx = find(u),fy = find(v);     if (fx == fy) return;     fa[fx] = fy; } //按秩合并 O(log2n) int fa[N],rk[N]; void init(int _n) {     rep(i,1,_n + 1)         fa[i] = i,rk[i] = 1;     //fa[i] = i;初始化情况下，每棵树的父亲均为自己 } //迭代写法 /* int find(int x) {     while (x != fa[x]) x = fa[x];     //如果不是树根，一步步往上查，x = fa[x]     return x; } */ //递归写法 int find(int x) {     if (x == fa[x]) return x;     return find(fa[x]); } void merge(int u, int v) {     //获得两棵树的父结点     int fx = find(u),fy = find(v);     //如果两个结点父亲一致，不做处理     if (fx == fy) return;     //如果不一致，操作如下     //交换操作，保证fx始终为树高小的那一棵     if (rk[fx] > rk[fy]) swap(fx,fy);     fa[fx] = fy;     //如果合并后两棵树的树高一致，新树高要加1     //即只有两棵树高为h的树才能合并出一棵树高为h + 1的树 T(h + 1) = 2 * T(h)     if (rk[fx] == rk[fy]) ++rk[fy]; }