0%

并查集

发表于 更新于 分类于

并查集问题

  • 用途:
    1. 查询两个元素是否属于一个集合
    2. 两个元素分别所在的集合合并
  • 代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    class UnionFindSet<T> where T: class
    {

        public UnionFindSet(params T[] arr)
        {
            this.father = new Dictionary<T, T>();
            this.size = new Dictionary<T, int>();
            foreach (T item in arr)
            {
                this.father[item] = item;
                this.size[item] = 1;
            }
        }

        private T GetFather(T value)
        {
            if (value == null)
            {
                return null;
            }
            T res = this.father[value];
            if (res != value)
            {
                this.size[res]--;
                res = GetFather(res);
            }
            else
            {
                this.size[res]--;
            }
            this.father[value] = res;
            this.size[res]++;
            return res;
        }

        public bool IsSameSet(T a, T b)
        {
            return this.GetFather(a) == this.GetFather(b);
        }

        public void Union(T a, T b)
        {
            if (a == null || b == null)
            {
                return;
            }
            T aHead = this.GetFather(a);
            T bHead = this.GetFather(b);
            if (aHead != bHead)
            {
                if (this.size[aHead] <= this.size[bHead])
                {
                    this.father[aHead] = bHead;
                    this.size[bHead] += this.size[aHead];
                }
                else
                {
                    this.father[bHead] = aHead;
                    this.size[aHead] += this.size[bHead];
                }
            }

        }

        private Dictionary<T, T> father;
        private Dictionary<T, int> size;
    }

例题: 岛问题:

  • 一个矩阵只有0和1两种值, 每个位置都可以和自己的上, 下, 左, 右四个位置相连, 如果有一片1连在一起, 这个部分叫做一个岛, 求矩阵中有多少个岛.

  • 矩阵 (此矩阵中有三个岛):
    0 0 1 0 1 0
    1 1 1 0 1 0
    1 0 0 1 0 0
    0 0 0 0 0 0

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public static int GetIsLandCount(int[][] m)
    {
        if (m == null || m.Length == 0 || m[0] == null || m[0].Length == 0)
        {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < m.Length; i++)
        {
            for (int j = 0; j < m[i].Length; j++)
            {
                if (m[i][j] == 1)
                {
                    res++;
                    Infect(m, i, j);
                }
            }
        }
        return res;
    }

    public static void Infect(int[][] m, int i, int j)
    {
        if (i < 0 || j < 0 || i > m.Length || j > m[i].Length || m[i][j] != 1)
        {
            return;
        }
        m[i][j] = 2;
        Infect(m, i - 1, j);
        Infect(m, i, j - 1);
        Infect(m, i + 1, j);
        Infect(m, i, j + 1);
    }

  • 当矩阵特别大, 需要划分并行时, 合并结果使用并查集

  • 思路:

    1. 将大矩阵分成若干块小矩阵, 放到不同的机器上计算
    2. 使用上面的算法来计算每个小矩阵的岛数
    3. 在修改值的时候记录一下该值是由那个方块引起的修改
    4. 合并的时候只需要考虑四个边界, 将起始方块修改一下并将岛的数量减一
    5. 当所有方块合并完成即可