如何在 Quick union 操作中 select 个元素？

Question

有一组元素 S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。这里有 10 个元素 (N = 10)。一个数组 arr 来管理元素的连接性。 Arr[ ] 由大小为 N 的集合元素索引（作为集合中的 N 个元素），用于管理 union 和 find 的操作。

https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/tutorial/

我不明白的是如何选择元素开始union运算？在这个 Link(上面提到) union 以 (2,1) 开始，我可以使用任何两个元素吗？说（1,8）？如果我开始选择不同的元素（除了 Union(2,1)），我似乎没有得到与图片中解释的相同的树。

Answer 1

您通常会根据要解决的任务的要求执行 Union 和 Find 操作。例如，一种测试无向图是否包含循环的方法是一条一条地考虑它的边。当考虑边 (u, v) 我们：

1. 提问：u和v是否已经连接？这转化为两个操作，Find(u) 和 Find(v).如果Find(u) = Find(v) , 那么边 (u, v) 是循环的一部分并且算法以答案 "yes".[=54 终止=]
2. 将u和v（以及它们各自的集合）标记为已连接，这样它们以后就不会再连接了。这转化为操作 Union(u, v).

最后，如果没有找到循环，算法将以答案 "no" 结束。