拉帮结派的数据结构-并查集

本文参考资源:

超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客

概述

并查集通常用作集合的合并。

并查集是一种树形结构,又叫“不相交集合”,保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员,通常选择根做这个代表。

我们先来介绍一下并查集的思想:

假设我们现在已知一些连通关系,例如(2,4),(1,2),(5,6),(3,4),(2,3),我们用一张图来表示这个关系:

现在我们用并查集的思想把它分成几个不连通的集合:

处理(2,4)

首先我们有一个father数组,它记录的是在并查集这个树形结构中,某个节点对应的父节点是哪个,用数组表示,一开始全为0。

我们把(2,4)这个关系取出来,每次要做的操作就是把它们的根节点连接起来(一直寻找父节点直到对应的father为0),这里就把4连接到2上,然后修改father[4]的值为2.

处理(1,2)

再处理(1,2)这个关系,由于此时1和2的根节点是它本身,也是将他们连起来。把father[1]修改为2。

处理(5,6)

5和6的根节点也是它本身,将他们连起来,father[6]修改为6。

处理(3,4)

这里发现3的根节点是3,4的根节点是2,于是把2和3连接起来。把father[2]修改为3。

最后处理(2,3)的时候发现2和3的根节点都是3,于是不做处理。 最后得到的集合有两个,分别是数组中值为0的3和5。

操作

上面的图中我们为了模拟自然思想,数组的下标从1开始,而实际编程的时候数组下标从0开始,根据限制可以把没有父节点的元素的值设为-1,也可以就设为该元素的下标,也可以把下标为0的数组元素空出来,对java来说就不用一开始就把数组赋一遍值。

并查集的核心操作有两个:

find_root(x):

返回能代表x所在集合的节点,通常返回x所在集合的根节点,有递归和非递归两种方法。

union(x, y):

将包含x,y的集合合并为一个新的集合。合并两个集合的关键是找到两个集合的根节点,如果两个根节点相同则不用合并;如果不同,则需要合并。

class UnionFind {
    int[] father;

    //构造函数,这里把它们全部赋值为-1,代表没有父节点
    public UnionFind(int totalNodes) {
        father = new int[totalNodes];
        Arrays.fill(father,-1);
    }

    //合并两个集合,即将它们的根节点连接。
    void union(int node1, int node2) {
        int root1 = find_root(node1);
        int root2 = find_root(node2);
        if (root1 != root2) {
            father[root2] = root1;
        }
    }

    // 找到一个数组元素对应的根节点
    int find_root(int node) {
        while (father[node] != -1) 
            node = father[node];
        return node;
    }

    //检查两个数组元素代表的集合是不是相连的,如果是说明它们的根节点是相同的
    boolean isConnected(int node1, int node2) {
        return find_root(node1) == find_root(node2);
    }
}

操作优化

并查集的优化主要包括:
+ 合并时平衡树的高度(比较要合并的两个树的高度)。
+ 查询时的优化:路径压缩

平衡树的高度这里不详细讲。

路径压缩就是每次查询的时候都会顺着路径查找,最终找到根节点。而找到了根节点之后可以将查询的节点的father直接连到根节点上,实际上也是减小树的高度。

拉帮结派的数据结构-并查集

算法题讲解

原题

蓝桥杯历届试题 合根植物

问题描述

w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?

输入格式

第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行,从上到下,从左到右编号。
比如:5 * 4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

样例输入

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

样例输出
5

样例说明

其合根情况参考下图

拉帮结派的数据结构-并查集

解答

这就是一道完全不加修饰,几乎要明示你这道题应该要用并查集的算法题。
按照我们之前的讲解,可以写出如下代码:

import java.util.Scanner;

public class Main {
    static int[] father;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //先算出数组的大小,这里我们从下标为1开始记录数据,就可以用0来代表没有父节点了。
        father = new int[scanner.nextInt()*scanner.nextInt()+1];
        int n = scanner.nextInt();
        for(int i = 0;i < n;i ++){
            union(scanner.nextInt(),scanner.nextInt());
        }
        int sum = 0;
        //看看合并完之后还有多少个没有父节点的元素,就是集合的个数
        for(int i = 1;i<father.length;i++){
            if(father[i] == 0) sum+=1;
        }
        System.out.println(sum);
    }

    //合并两个集合,即将它们的根节点连接。
    static void union(int node1, int node2) {
        int root1 = find_root(node1);
        int root2 = find_root(node2);
        if (root1 != root2)
            father[root2] = root1;
    }

    // 找到一个数组元素对应的根节点,这里由于整道题我们只需要查找一次就不优化了。
    static int find_root(int node) {
        while (father[node] != 0)
            node = father[node];
        return node;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e6%8b%89%e5%b8%ae%e7%bb%93%e6%b4%be%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%b9%b6%e6%9f%a5%e9%9b%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月17日 13:56
下一篇 2020年2月18日

相关推荐

  • leetcode28-实现strStr()

    原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从…

    算法 2019年11月20日
    0110
  • leetcode122-买卖股票的最佳时机II

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意: 你不能同…

    算法 2020年2月7日
    080
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0110
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode72-编辑距离

    原题 给你两个单词 word1 和 word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字…

    2020年4月6日
    0110
  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例2: 输入: n…

    算法 2019年12月28日
    0140
  • leetcode206-反转链表

    原题 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法…

    2019年12月16日
    0150
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0120

发表回复

登录后才能评论