并查集——并查集的优化
查询优化 路径压缩 很显然，我对我的爸爸或者爷爷是谁并不在乎，我只在乎我的祖先是谁。 根据这样的思路，路径压缩的并查集就诞生了 int find(int x) { if (x != fa[x]) // x不是自身的父亲，即x不是该...
查询优化 路径压缩 很显然，我对我的爸爸或者爷爷是谁并不在乎，我只在乎我的祖先是谁。 根据这样的思路，路径压缩的并查集就诞生了 int find(int x) { if (x != fa[x]) // x不是自身的父亲，即x不是该...
对于并查集的定义其实并不难理解 通俗的理解可以是：你是我的亲戚，他是我的亲戚，那你和他同样也是亲戚。通过合并而查索之的操作，可以实现在较小的时间复杂度下完成对一些不交集的 合并 及 查询 问题 ...