第14课：路径压缩
进度 0/24
🚀
路径压缩
一次深爬，终身直达！
📖知识引入
😰长链问题
集合 unlucky 连成一条长链，find要一步一步爬，越爬越慢
🚀路径压缩
找根的途中，把沿途节点全部直接挂到根上，一步到位
📉效果惊人
树被压得又扁又平，之后的查询几乎一步就到根
🔁一行写法
return fa[x] = find(fa[x])，递归一行完成压缩
💡
路径压缩只改find函数一行，代价几乎为零，信奥实战必带
🔍带路径压缩的find
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]); // 边找根边把 x 挂到根上
}
// 压缩前：1 ← 2 ← 3 ← 4，找 4 的根要爬 3 步
// 压缩后：2、3、4 都直接挂在 1 下面，再查只走 1 步递归找根的同时把沿途节点都挂到根上，下次查询直达。
🎯小测验
第1题：路径压缩发生在哪个操作里？
第2题：路径压缩后并查集的树变得更？
第3题：一行递归压缩的标准写法是？
📝本课知识点
- ✓压缩=沿途挂到根
- ✓一行代码搞定
- ✓查询几乎O(1)
第14课完成！继续探索下一课吧 🚀