算法----并查集合

并查集合字面意思，合并，查询，集合。

why

为什么要使用它，什么题适用于这个算法。

一般当我们在考虑图联通的时候就可以考虑一下使用并查集。他跟图密切相关。

what

并查集主要是什么。

我们一般使用一个集合来存放图中的各个节点。

然后初始化让这个集合里的元素是他自己，这里形象的形容让他自己成为自己的领导。

然后当一个节点要和另一个节点相连的时候，我们就要先去查询他们的最高级领导，找到他们的最高级领导后，在他们的最高级领导中选择一个成为他们两个最高级领导的更高级领导（也就是合并两个元素）。

how

如何去使用并查集

并查集严格按照他的名字来。

一般是先new一个数组（集合），然后让这个数组初始化。

int[] set = new int[n];
for (int i = 0; i < n; i++) {
    set[i] = i;
}

然后就是查的方法，去查找一个节点的最高级领导。在这个集合里面，只有自己的索引等于自己的元素的才是最高级领导。

public int find(int x,int[] set){
        if (x == set[x]){
            return x;
        }
        return find(set[x],set);
}

最后就是并的方法，找到他们的最高级领导后，选出其中一个领导成为更高级领导。

public void union(int x,int y,int[] set){
        set[y] = x;
}

这些就是并查集的核心思想，掌握好这个思想只要是关于并查集的问题都能根据实际轻微修改很快的做出来。