第13课：并查集的概念
进度 0/24
🤝
并查集的概念
朋友的朋友也是朋友，大家连成一片！
📖知识引入
🤝并查集干嘛
高效回答“x和y是否在同一个集合”，还能随时合并两个集合
🗂️fa数组
fa[x]存x的上级，一路向上找到集合的大当家——根
🔗合并操作
把一个集合的根挂到另一个集合的根下面，两家变一家
⚡近乎O(1)
配合路径压缩，查询和合并快到几乎不花时间
💡
初始化时fa[i]=i，让每个元素自成一个集合，自己就是自己的代表
🔍并查集三件套
int fa[10005];
int find(int x) { // 找 x 所在集合的根
while (fa[x] != x) x = fa[x];
return x;
}
void unite(int x, int y) { // 合并两个集合
fa[find(x)] = find(y); // x 的根挂到 y 的根下面
}
// 使用前初始化：for (int i = 1; i <= n; i++) fa[i] = i;初始化、找根、合并，三段代码撑起并查集的全部骨架。
🎯小测验
第1题：并查集最擅长解决什么问题？
第2题：初始化时fa[i]应该等于？
第3题：合并x和y所在集合的正确写法是？
📝本课知识点
- ✓fa数组存上级
- ✓find找到集合的根
- ✓合并=根挂根
第13课完成！继续探索下一课吧 🚀