树、森林——树与二叉树的应用（并查集的基本实现）

一、初始化用一维数组parent[]每个元素自己是一个独立集合plaintextparent[i] -1根结点标记-1二、查找操作 Find找根递归 / 循环找结点最终祖先若parent[x] -1→ x 就是根否则继续找parent[x]的根路径压缩必优化查找路上所有结点直接指向根树变扁平速度极快int find(int x){ if(parent[x] ! -1) parent[x] find(parent[x]); //路径压缩 return parent[x]; }三、合并操作 Union分别找到 a、b 的根 root1、root2若根不同不属于同一集合让一个根的双亲 另一个根void union(int a,int b){ int ra find(a); int rb find(b); if(ra ! rb) parent[rb] ra; }按秩合并优化额外rank[]存树高度矮树挂高树防止树过高退化四、判断是否同集合if(find(a) find(b)) 同一集合else 不同集合五、考点总结结构双亲表示法 一维数组无路径压缩O (logn)路径压缩 按秩合并近似 O (1)用途Kruskal 最小生成树、判断连通分量