之所以使用 parent 存储每个节点的父节点,而不是使用 children 存储每个节点的子节点是因为“我们需要找到某个元素的代表(也就是根)”
find
,connnected
和 union
, 的形象化解释,下面我们来看下代码实现。这里的代表就是上面的“司令”。
树的根
在 parent 中满足“parent[x] == x”。因此我们可以先找到 0 的父亲 parent[0] 也就是 1,接下来我们看 1 的父亲 parent[1] 发现是 3,因此它不是根,我们继续找 3 的父亲,发现是 3 本身。也就是说 3 就是我们要找的代表,我们返回 3 即可。注意是趋近 O(1),准确来说是阿克曼函数的某个反函数。
union(0, 7)
,则会发生如下过程。weight[a] = 1 表示 a 到其父节点的权重是 1
。并查集
标签,但是使用并查集来说确非常简单。这类题目如果掌握模板,那么刷这种题会非常快,并且犯错的概率会大大降低,这就是模板的好处。