算法学习笔记——专题拓展5：并查集（Union-find）算法

介绍

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法，同时它也是最小生成树算法的前置知识。

模板代码

class UF{
    private:
        int count;
        int* parent;

    public:
        UF(int n){
            this->count = n;
            this->parent = new int[n];
            for(int i = 0; i<n; i++){
                parent[i] = i;
            }
        }

        void union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP == rootQ){
                return;
            }
            parent[rootP] = rootQ;
            count--;
        }

        //使用了路径压缩，所以不需要size数组来平衡二叉树了
        int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        bool connected(int p, int q){
            return find(p) == find(q);
        }

        int count(void){
            return count;
        }
}

题目

例题1：最大人工岛

分析：

代码：

例题2：被围绕的区域

分析：

代码：

例题3：等式方程的可满足性

分析：

代码：

例题4：

分析：

代码：

总结