题目：
问题描述
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
样例说明
其合根情况参考下图
分析：
一开始我看到这是考察并查集的题目，就直接往这方面想，因为这题也是解决合并与查询的问题，所以用并查集是肯定的，但是要用哪种数据结构来表示所有集合呢，这里我构造了二叉排序树用来存储每个集合的所有元素，然后针对每次输入的两个数之间的关系，将这两个数所在的集合合并，不过要先判断这两个数是否在一个集合中，如果在就不用操作，反之则进行上面所说的操作，每次合并完之后，就要将另一个树中的所有元素对应在dp数组中的值修改为合并的那棵树对应在dp数组中的值。即dp[b] = dp[a]，等接收完所有可能合根的情况之后，就计算一下arr数组中还剩下哪些不为null的集合，将统计之后的结果输出即可。这个算法经蓝桥官网的OJ测试之后，最后得了60来分，我分析原因，应该是我的二叉树在查询与合并的操作上效率会有点低。
上代码：
1 package com.lzp.lanqiaocontests; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Scanner; 6 7 /** 8 * @Author LZP 9 * @Date 2021/3/19 11:59 10 * @Version 1.0 11 * 题目描述 12 * 13 * w 星球的一个种植园，被分成 m×n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。 14 * 15 * 这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。 16 * 17 * 如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？ 18 * 输入描述 19 * 20 * 第一行，两个整数 m,n，用空格分开，表示格子的行数、列数（1≤m,n≤10000）。 21 * 22 * 接下来一行，一个整数 k (0≤k≤10^5 )，表示下面还有 k 行数据。 23 * 24 * 接下来 k 行，第行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。 25 * 26 * 格子的编号一行一行，从上到下，从左到右编号。 27 * 28 * 比如：5×4 的小格子，编号： 29 * 30 * 1 2 3 4 31 * 5 6 7 8 32 * 9 10 11 12 33 * 13 14 15 16 34 * 17 18 19 20 35 * 输出描述 36 * 37 * 输出植物数量。 38 * 输入输出样例 39 * 示例 40 * 41 * 输入 42 * 5 4 43 * 16 44 * 2 3 45 * 1 5 46 * 5 9 47 * 4 8 48 * 7 8 49 * 9 10 50 * 10 11 51 * 11 12 52 * 10 14 53 * 12 16 54 * 14 18 55 * 17 18 56 * 15 19 57 * 19 20 58 * 9 13 59 * 13 17 60 * 61 * 输出 62 * 5 63 * 64 * 样例说明 65 * 66 * 其合根情况参考下图： 67 * 68 * 运行限制 69 * 70 * 最大运行时间：2s 71 * 最大运行内存: 256M 72 * 73 * 该题使用并查集解，每当输入一对可以合根的植物，就将这两个植物所在的集合合并，直到 74 * 所有合根的情况都已经输入完成，就确定了这片田地中最终剩下多少根植物，也就是求最 75 * 终剩下的有几个集合，这里的集合我们用树来表示 76 */ 77 public class MergePlant { 78 /** 79 * dp[i] = val 表示数i此时处在索引为val的位置 80 */ 81 private static int[] dp = new int[1000000 + 10]; 82 private static Node[] arr = new Node[1000000 + 10]; 83 public static void main(String[] args) { 84 Scanner input = new Scanner(System.in); 85 int m = input.nextInt(); 86 int n = input.nextInt(); 87 for (int i = 1; i <= m * n; i++) { 88 // 一开始，将每个植物都作为一个集合，把自己装入 89 Node root = new Node(i, null, null); 90 arr[i] = root; 91 dp[i] = i; 92 } 93 94 int k = input.nextInt(); 95 // 接收所有合根的情况 96 for (int i = 0; i < k; i++) { 97 int a = input.nextInt(); 98 int b = input.nextInt(); 99 // 将b中的所有数用List集合存储起来，后面会用的到 100 List<Integer> list = new ArrayList<>(); 101 if (!find(a, b)) { 102 103 // 判断两者能否合根，因为题目说了：这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。 104 // 言外之意就是，斜的对角线是不可以的 105 106 // a、b不在同一棵树中 107 Node rootA = arr[dp[a]]; 108 Node rootB = arr[dp[b]]; 109 if (rootA != null && rootB != null) { 110 union(rootA, rootB, list); 111 // 修改dp[b]中的所有值为dp[a] 112 for (int j = 0; j < list.size(); j++) { 113 dp[list.get(j)] = dp[a]; 114 // 置为null 115 arr[list.get(j)] = null; 116 } 117 } 118 } 119 } 120 121 int count = 0; 122 for (int i = 1; i <= m * n; i++) { 123 // 如果不为arr[i] != null ，则表示i这棵植物还在，没有被其他植物合根， 124 if (arr[i] != null) { 125 count++; 126 } 127 } 128 System.out.println(count); 129 } 130 131 /** 132 * 查询两个数是否在同一棵树中 133 * @param a 134 * @param b 135 * @return 136 */ 137 public static boolean find(int a, int b) { 138 return dp[a] == dp[b]; 139 } 140 141 /** 142 * 将b树中的所有元素都添加到a树中 143 * @param a 144 * @param b 145 * @return 146 */ 147 public static Node union(Node a, Node b, List<Integer> list) { 148 BinarySortTreeUtil.getValues(b, list); 149 for (int i = 0; i < list.size(); i++) { 150 BinarySortTreeUtil.add(a, list.get(i)); 151 } 152 return a; 153 } 154 } 155 156 157 /** 158 * 二叉排序树 159 */ 160 class BinarySortTreeUtil { 161 162 public static void add(Node root, int data) { 163 if (!find(root, data)) { 164 addNode(root, data); 165 } 166 } 167 168 /** 169 * 中序遍历 170 * @param root 171 * @param list 172 */ 173 public static void getValues(Node root, List<Integer> list) { 174 if (root == null) { 175 return; 176 } 177 if (root.left != null) { 178 getValues(root.left, list); 179 } 180 list.add(root.data); 181 if (root.right != null) { 182 getValues(root.right, list); 183 } 184 } 185 186 /** 187 * 添加元素 188 * 如果要添加的元素跟二叉树中的某一个元素相等则不添加 189 * @param root 190 * @param data 191 */ 192 private static void addNode(Node root, int data) { 193 if (data < root.data) { 194 if (root.left == null) { 195 // 如果左孩子为空，则直接赋值给左孩子 196 root.left = new Node(data, null, null); 197 } else { 198 // 左孩子 199 addNode(root.left, data); 200 } 201 } else if (data > root.data){ 202 if (root.right == null) { 203 // 如果右孩子为空，则直接赋值给右孩子 204 root.right = new Node(data, null, null); 205 } else { 206 // 右孩子 207 addNode(root.right, data); 208 } 209 } 210 } 211 212 /** 213 * 二分查找 214 * @param data 215 * @return 216 */ 217 public static boolean find(Node root, int data) { 218 if (root == null) { 219 return false; 220 } 221 if (data == root.data) { 222 return true; 223 } else if (data < root.data) { 224 return find(root.left, data); 225 } else { 226 return find(root.right, data); 227 } 228 } 229 } 230 231 232 /** 233 * 二叉树节点 234 */ 235 class Node { 236 public int data; 237 public Node left; 238 public Node right; 239 240 public Node(int data, Node left, Node right) { 241 this.data = data; 242 this.left = left; 243 this.right = right; 244 } 245 }