2018-03-03 16:00:40
集合运算： 交、并、补、差，判定一个元素是否属于某一集合。
并查集：集合并 、查某元素属于哪个集合。
并查集问题中集合存储如何实现？
1）可以用树结构表示集合，树的每个结点就是集合中的各个元素。
2）采用数组的形式进行存储
- 查找操作
- 集合并操作
这里的并操作是不加判断对的将X2所在的集合直接挂到X1上，这种操作很有可能造成X1的深度不断增加，最终导致查找效率的低下。因此可以略作改进，将集合的并操作加上一个限制，就是将规模较小的集合并到规模较大的集合中去。至于如何的到集合的规模信息，可以采用一种非常讨巧的方式，将原来的-1修改为规模的相反数。
