并集怎么理解

来源：11-2 Quick Find

慕粉3520842

2019-01-07

波波老师你好。
对这一段我有疑问：既然这里取的是并集，为什么在两个元素取并集的时候，是取其中一个元素的集合，另一个的集合被扔掉了。
这样并完了之后，10个元素的集合就剩1或0了。
还是说这里的并集并不是数学中的并集？

写回答

3回答

liuyubobobo

2019-01-09

已采纳

并查集的并不是把两个元素并在一起，是把两个元素所在的集合并在一起。只不过在初始的条件下，所有的元素都是单独自己各自在一个集合中。随着不断的调用unionElements，元素所在的集合在不断“合并”。

可以尝试使用课程的并查集代码进行如下实验：

public static void main(String[] args) {
    
    // 我直接使用这一张最后的UnionFind5进行试验，但是其他版本的UnionFind也是成立的
    // 我们只创建包含有3个元素的并查集
    UnionFind5 uf = new UnionFind5(3);
    
    uf.unionElements(0, 1); // 合并0所在的集合和1所在的集合
                            // 初始0和1两个元素所在的集合都只有1个元素
                            // 所以合并后的集合只包含两个元素
    uf.unionElements(1, 2); // 和并1所在的集合和2所在的集合
                            // 注意：此时由于1所在的集合有2个元素(0和1)
                            // 所以，合并后，0, 1, 2三个元素在同一个集合中
                            
    // 为了验证，我们查看一下0和2是不是在一个集合中？
    // 输出为true :-)
    System.out.print(uf.isConnected(0, 2));
}

请在仔细理解一下，课程中的并查集的实现，是怎么做到这一点的？：）

加油！：）

慕粉3520842

非常感谢！

2019-01-09

共1条回复