并查集算法 详解

并查集的思想

并查集是一种树形的数据结构，用于处理不相交集的合并查询，一般具有两个基本的操作，查找确定元素在哪一个子集，合并将两个子集进行合并。

并查集的两个优化是路径压缩和启发式的合并。

金典应用是最小生成树和最大公共祖先，检测图是否有环。

并查集的构建

/*
      并查集是一个数组，每一个值保存一个父节点，形成一个集合，
      集合需要关注两个操作，查找父节点，合并
     */
    public int find(int[] parents, int d){
        int f_root = d;
        while (parents[f_root] != -1){
            d = parents[f_root];
        }
        return f_root;
    }
    
    // 合并集合，合并集合最简单的操作是将其父节点进行关联
    public int union(int[] parents, int x , int y){
        int x_root = find(parents,x);
        int y_root = find(parents,y);
        if(x_root == y_root){
            return 0;
        }
        parents[x_root] = y_root;
        return 1;
    }

第二种方式作为内部类进行使用

static class DUS{
        int[] parent;
        public DUS(int n){
            parent = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = i;
            }
        }
        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if (x_root == y_root){
                return 0;
            }
            if (x_root < y_root){
                parent[y_root] = x_root;
            }else {
                parent[x_root] = y_root;
            }
            return 1;
        }
    }

// 三种启发式合并，避免形成的树过深

   class DSU {
        int[] parent;
        int[] rank;
        int N = 6;

        public DSU() {
            parent = new int[N];
            rank = new int[N];
            for(int i=0;i<N;i++){
                parent[i] = i;
            }
        }

        // 这里顺便做路径压缩，将查到的父节点赋值给当前节点
        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if(x_root == y_root){
                return 0;
            }
            // 将大指向小进行统一
            // 使用启发式合并，避免形成的树过深
            if(rank[x_root] < rank[y_root]){
                parent[x_root] = y_root;
            }else if (rank[x_root] > rank[y_root]){
                parent[y_root] = x_root;
            }else{
                rank[x_root]++;
                parent[y_root] = x_root;
            }
            return 1;
        }
    }

eg 题目

判断图是否有环

思路是，选择边，如果当前的边的点存在集合有加入对应集合，否则开辟新集合，如果存在两个集合有的将两个集合进行合并，如果加入的点都在一个集合里，说明存在环。

1559. 二维网格图中探测环

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

输出：true

class Solution {
     static class DUS{
        int[] parent;
        public DUS(int n){
            parent = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = -1;
            }
        }
        public int find(int x){
            while(parent[x] != -1){
                x = parent[x];
            }
            return x;
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if (x_root == y_root){
                return 0;
            }
            if (x_root < y_root){
                parent[y_root] = x_root;
            }else {
                parent[x_root] = y_root;
            }
            return 1;
        }
    }

    // 思路将二维数组当做一维数组，做并查集，判断存在环,将一个边的两个点加入并查集
    // 将一个边的两个点加入并查集

    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        DUS dus = new DUS(m*n);
        for(int i=0;i<m;i++){
            for(int j=1;j<n;j++){
                if(grid[i][j-1] == grid[i][j]){
                    int u = dus.union(i * n + j, i * n + j - 1);
                    if (u == 0){
                        return true;
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++){
                if(grid[j-1][i] == grid[j][i]){
                    int u = dus.union((j-1) * n + i, j * n + i);
                    if (u == 0){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]

class DUS {
        int[] parent;
        public DUS (int n){
            parent = new int[n+1];
            for (int i=1;i<=n;i++){
                parent[i] = i;
            }
        }

        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if (x_root == y_root){
                return 0;
            }
            if (x_root < y_root){
                parent[y_root] = x_root;
            }else {
                parent[x_root] = y_root;
            }
            return 1;
        }

    }


    public  int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        DUS dus = new DUS(n);
        for (int[] nums: edges){
            int i = dus.union(nums[0],nums[1]);
            if (i == 0){
                return nums;
            }
        }
        return new int[0];
    }

统计图形成联通集的个数

思路在向并查集中添加完所有的边对应的点后，统计现在是顶点的个数，一个顶点是一个联通图，parent[i] = i

包括统计每一个联通图里面节点的个数

547 朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1：

输入：
[[1,1,0],
[1,1,0],
[0,0,1]]

输出：2
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。

class Solution {

    // 思路形成并查集，并将其所有节点都标记为父节点，统计父节点的个数
    // 初始让所有节点父节点是本身

    class DUS{
        int[] parent;
        public DUS(int n){
            parent = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = i;
            }
        }

        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if(x_root == y_root){
                return 0;
            }
            if(x_root < y_root){
                parent[y_root] = x_root;
            }else{
                parent[x_root] = y_root;
            }
            return 1;
        }

        public int getRootNum(){
            int count = 0;
            for(int i=0;i<parent.length;i++){
                if(parent[i] == i){
                    count++;
                }
            }
            return count;
        }
    }

    public int findCircleNum(int[][] M) {
        int n = M.length;
        DUS dus = new DUS(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(M[i][j] == 1 && i != j){
                    dus.union(i,j);
                }
            }
        }
        return dus.getRootNum();
    }
}
959. 由斜杠划分的区域

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\" 表示。）。

返回区域的数目。

 public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        DSU dsu = new DSU(4 * N * N);
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r].charAt(c);
                if (val != '\\') {
                    dsu.union(root + 0, root + 1);
                    dsu.union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.union(root + 0, root + 2);
                    dsu.union(root + 1, root + 3);
                }

                // north south
                if (r + 1 < N)
                    dsu.union(root + 3, (root + 4 * N) + 0);
                if (r - 1 >= 0)
                    dsu.union(root + 0, (root - 4 * N) + 3);
                // east west
                if (c + 1 < N)
                    dsu.union(root + 2, (root + 4) + 1);
                if (c - 1 >= 0)
                    dsu.union(root + 1, (root - 4) + 2);
            }

        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x)
                ans++;
        }

        return ans;
    }
}

class DSU {
    int[] parent;

    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}
17.07 婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择字典序最小的名字作为真实名字。

示例：

输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]

static class DUS {
        int[] parent;
        public DUS (int n){
            parent = new int[n];
            for (int i=0;i<n;i++){
                parent[i] = i;
            }
        }

        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if (x_root == y_root){
                return 0;
            }
            if (x_root < y_root){
                parent[y_root] = x_root;
            }else {
                parent[x_root] = y_root;
            }
            return 1;
        }

    }


    // 将孩子的名字编号，并将其次数统计出来
    public static String[] trulyMostPopular(String[] names, String[] synonyms) {
        List<String> nameList = new ArrayList<String>();
        HashMap<String,Integer> map = new HashMap<String, Integer>();

        for(String item: names){
            int idx = item.indexOf("(");
            String sub = item.substring(idx+1,item.length()-1);
            String name = item.substring(0,idx);
            nameList.add(name);
            map.put(name,Integer.parseInt(sub));
        }
        Collections.sort(nameList);
        DUS dus = new DUS(nameList.size());
        for (String pair: synonyms){
            String[] pairs = pair.substring(1,pair.length()-1).split(",");
            int x = nameList.indexOf(pairs[0]);
            int y = nameList.indexOf(pairs[1]);
            if (x== -1 || y == -1) continue;
            dus.union(x, y);
        }
        HashMap<String, Integer> res = new HashMap<String, Integer>();
        for (int i=0;i<nameList.size();i++){
            int root = dus.find(i);
            String originName = nameList.get(i);
            String rootName = nameList.get(root);
            res.put(rootName, res.getOrDefault(rootName,0) + map.get(originName));
        }
        List<Map.Entry<String,Integer>> list = new ArrayList<>(res.entrySet());
        String[] result = new String[res.size()];
        int idx = 0;
        for (Map.Entry<String,Integer> entry: list){
            result[idx++] = entry.getKey() + "(" + entry.getValue() + ")";
        }
        return result;
    }

判断两个点是不是同一个联通集里面的

判断两个点是不是同一个联通集里面的，先将形成联通集的加入形成最终的联通集，最后将判断节点依次判断父节点是否相同

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

    // 使用并查集，将小的作为父节点，
    class BUS {
        int[] parent;
        int N = 26;
        public BUS(){
            parent = new int[N];
            for(int i=0;i<N;i++){
                parent[i] = i;
            }
        }

        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public int union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if(x_root == y_root){
                return 0;
            }
            if(x_root < y_root){
                parent[y_root] = x_root;
            }else{
                parent[x_root] = y_root;
            }
            return 1;
        }
    }

    public boolean equationsPossible(String[] equations) {
        BUS bus = new BUS();
        for(String item : equations){
            int x = item.charAt(0) - 'a';
            int y = item.charAt(3) - 'a';
            char c = item.charAt(1);
            if(c == '='){
                bus.union(x,y);
            }
        }
        for(String item : equations){
            int x = item.charAt(0) - 'a';
            int y = item.charAt(3) - 'a';
            char c = item.charAt(1);
            if(c == '!'){
            int x_root = bus.find(x);
            int y_root = bus.find(y);
            if(x_root == y_root){
                return false;
            }
            }
        }
        return true;
    }
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 221,820评论 6赞 515
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 94,648评论 3赞 399
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 168,324评论 0赞 360
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 59,714评论 1赞 297
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 68,724评论 6赞 397
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 52,328评论 1赞 310
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,897评论 3赞 421
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,804评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 46,345评论 1赞 318
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,431评论 3赞 340
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,561评论 1赞 352
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 36,238评论 5赞 350
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,928评论 3赞 334
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,417评论 0赞 24
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,528评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,983评论 3赞 376
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,573评论 2赞 359