并查集算法（内含Kruscal算法的Java ACM模式实现代码）

1、用集合中的某个元素来代表这个集合，则该元素称为此集合的代表元；
2 、一个集合内的所有元素组织成以代表元为根的树形结构；
3 、对于每一个元素 x，pre[x] 存放 x 在树形结构中的父亲节点（如果 x 是根节点，则令pre[x] = x）；
4 、对于查找操作，假设需要确定 x 所在的的集合，也就是确定集合的代表元。可以沿着pre[x]不断在树形结构中向上移动，直到到达根节点。
因此，基于这样的特性，并查集的主要用途有以下两点：
1、维护无向图的连通性（判断两个点是否在同一连通块内，或增加一条边后是否会产生环）；
2、用在求解最小生成树的Kruskal算法里。

一般来说，一个并查集对应三个操作：
1、初始化（ Init()函数 ）
2、查找函数（ findParent()函数 ）
3、合并集合函数（ union()函数 ）

在学习Kruscal算法的时候，了解到该算法的大致流程是对图中的边进行排序，每次取出权值最小的边加入图中，且加入之后图中不能出现环，此时就需要运用到并查集算法来判断加入一条边后是否成环。（PS：查阅网上资料后，发现并没有比较完整的答案或者可以直接应用到算法题的解析，于是参考网上大佬的思路，自己实现了一个Kruscal算法）。代码如下：

题目：给你n个点，m条边，后面为边的权值，实现kruskal算法。
如：
6
10
0 1 6
0 2 1
0 3 5
2 1 5
2 3 5
2 4 5
2 5 4
1 4 3
4 5 6
5 3 2
//定义边    
class Edge{
    int x;
    int y;
    int weight;
    Edge(){};

    public Edge(int x, int y, int weight) {
        this.x = x;
        this.y = y;
        this.weight = weight;
    }
}
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Edge[] edges = new Edge[m];
        for(int i = 0 ; i < m ; i++){
            edges[i] = new Edge();
            edges[i].x = sc.nextInt();
            edges[i].y = sc.nextInt();
            edges[i].weight = sc.nextInt();
        }
        sc.close();
        List result = function(edges,n);
        for(Edge edge : result){
            System.out.print(edge.x);
            System.out.print(" " + edge.y);
            System.out.println(" " + edge.weight);
        }
    }
    private static List function(Edge[] edges,int n){
        //小顶堆对边的权值进行排序
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        for(Edge edge : edges){
            queue.offer(edge);
        }
        UnionCollection uc = new UnionCollection(n);
        List result = new ArrayList<>();
        while(!queue.isEmpty()){
            Edge edge = queue.poll();
            int node1 = edge.x;
            int node2 = edge.y;
            if(uc.union(node1,node2)){
                result.add(edge);
            }
        }
        return result;
    }
 //并查集模板
 class UnionCollection{
    int n ;
    int[] size;
    int[] parent;
    int count;

    UnionCollection(int n){
        this.n = n;
        this.size = new int[n];
        this.parent = new int[n];
        this.count = n;

        Arrays.fill(size,1);
        for(int i = 0 ; i < n ; i++){
            parent[i] = i;
        }
    }
    public int findParent(int x){
        if(parent[x] == x){
            return x;
        }else{
            parent[x] = findParent(parent[x]);
            return parent[x];
        }
    }
    public void union(int x , int y){
        int parentx = findParent(x);
        int parenty = findParent(y);
        if(parentx == parenty){
            return;
        }else{
            if(size[parentx] > size[parenty]){
                int temp = parentx;
                parentx = parenty;
                parenty = temp;
            }
            parent[parentx] = parenty;
            count--;
            size[parenty] += size[parentx];
            return;
        }
    }
    public boolean isConnected(int x , int y){
        int parentx = findParent(x);
        int parenty = findParent(y);
        return parenty == parentx;
    }
}

附上两道leetcode上关于并查集的练习题：

leetcode-1319-连通网络的操作次数

leetcode-547-省份数量