题目现在有 个元素分为若干个集合。需要支持两种操作合并操作(1)将 和 所在的集合合并为一个集合查询操作(2)查询 和 是否在同一个集合中输入格式第一行, 个元素 次操作接下来 行每行三个整数 ,,若 1合并 , 所在集合若 2查询 , 是否同属一个集合输出格式对每个查询操作2输出Y或N约束条件1≤≤1051≤≤1051≤,≤ 核心思路每个点都是一颗树的节点相同集合的点的根相同指向同一个数并查集 树结构 找根find 合并union 路径压缩优化 模板步骤初始化树rep(i,1,n1) fa[i]i;//每个节点的fa都是自己 每个循环输入x,y 先找到他们各自的根 xfind(x),yfind(y); 如果合并把y的根节点指向x的根节点 xfa[y]; 否则判断两者的根是否相同 找根节点find函数实现 ## 优化点 使用递归可将沿路的的节点的父节点都指向根节点 使树的深度接近常数级提升后续查询效率 int find(int x){ if(fa[x]x) return x; return fa[x]find(fa[x]); }代码实现完整代码const int N2e55; int a[N]; int find(int x){ if(xfa[x]) return x; return fa[x]find(fa[x]); } void solve(){ int n,m; cinnm; rep(i,1,n1) fa[i]i; int x,y,z; while(m--){ cinz; xfind(x); yfind(y); if(z1){ xfa[y]; } else { if(xy) coutY\n; else coutN\n; } } } 复杂度分析指标值说明总时间(())m次操作空间复杂度()fa数组复杂度说明没有路径压缩时find 时间复杂度为 ()总体为 ()容易超时使用路径压缩后单次操作时间复杂度降低到 (())≈(1)反阿克曼函数 () 增长极慢(105)4实际上几乎是常数 总结结构本质并查集用树的结构表示集合关系根节点唯一标识一个集合