并查集的实现与性能优化

并查集是用于处理不相交集合的合并及查询问题,主要操作为:创建集合、合并两个不相交集合、判断两个元素是否属于同一个集合。

其中,判断两个元素是否属于同一个集合,可以这样考虑:为每个集合选一个代表元素,从而“判断两个元素是否属于同一个集合”就变成了“判断两个元素所在集合的代表元素是否相同”。

基本操[......]

阅读全文