【笔记】数据结构与算法之并查集（UnionFind）

QingYi.

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x)Find(x)Find(x) 返回 xxx 所属集合的代表，而 Union 使用两个集合的代表作为参数。

直接上并查集代码，注释都在代码里面。

public class Main {
    // size and compress
    static class UnionFind{
        // p is parentNode
        int [] p ;
        int [] size;
        public  UnionFind(int n ){
            //空着第一个元素
            p = new int[n+1];
            size = new int[n+1];
            for (int i = 1;i<=n;i++){
                p[i] = i;
                size[i]=1;
            }
        }
        public int getSize(){
            return p.length;
        }
        public int find(int x){
            if(x != p[x])
            {
                int t = find(p[x]); //寻找根结点，找到后回溯
                p[x] = t; //路径压缩
                //上面的部分可以这写成
//                p[x] = find(p[x]);
            }
            return p[x];
        }
        public void union(int x , int y){
            int rootX = find(x);
            int rootY = find(y);
            //如果两个节点的父亲节点是一样的话 就直接return 不处理
            if (rootX==rootY){
                return;
            }
            /**
             * 把size 小的拼接到size大的树上，避免树的深度过高
             */
            if (size[rootX]<size[rootY]) {
                //rootX 的父亲节点就变成了 rootY 也就是挂接到rootY上了
                p[rootX] = rootY;
                //roorY的大小就加等于rootX的大小了
                size[rootY] +=size[rootX];
            }else {
                p[rootY] = rootX;
                size[rootX]+=size[rootY];
            }
        }
    }
}

QingYi.

@alittlebear 今天不学习 明天变垃圾

码上

感谢分享，但是更喜欢c++刷题

QingYi.

码上 发表于 2020-11-30 23:20
感谢分享，但是更喜欢c++刷题

哈哈哈，上学的时候c++没学好，哎，一大遗憾