算法题库 合根植物

题目

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

其合根情况参考图[p1.png]

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

解题思路

1、有点类似于并查集的子问题。创建一个数组将植物编号为key，所属集合编号为value。这里只列出前10个。因为植物编号从1开始而数组从0开始故id[0]代表编号为1的植物，id[1]代表编号为2的植物。初始默认没有和根，故默认每个植物对应一个集合。
下面列出植物编号1-10对应的数组表。

2：假如编号2，3合根则将植物3的集合编号改为植物2的集合编号 ;
减一原因是因为植物编号从1开始数组则是从0开始。
更新后的id数组表
备注：假如0，1进行合并。将集合编号进行更改时需将所有集合编号为1的值改为0.并集是两个集合的合并并不是单单两个元素的合并

3:进行完所有的合根操作后遍历数组，统计一共有多少个集合。输出结果ps:在进行合并操作时有很大的优化空间，这里为了便于理解并未优化。优化后的代码放在文末。具体思路以后有时间再慢慢补充。。。。。。

//java代码private static int [] id;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int m=scanner.nextInt();int n=scanner.nextInt();id=new int[m*n];//m*n代表一共有多少植物//初始化集合idfor (int i = 0; i <id.length ; i++) {id[i]=i;}int k=scanner.nextInt();//进行k次合并操作for (int i = 0; i <k ; i++) {int a=scanner.nextInt();int b=scanner.nextInt();union(a,b);//合根操作}//遍历数组获取集合数量，利用HashSet不保存相同元素的特性。HashSet set=new HashSet();for (int i = 0; i <id.length ; i++) {set.add(id[i]);}//输出集合数量System.out.println(set.size());}//合并private static void union(int a,int b){int aid=id[a-1];//获取a植物所在集合的编号int bid=id[b-1];//获取b植物所在集合编号for (int i = 0; i <id.length ; i++) {if (id[i] == bid) {//获取数组中b集合的元素。id[i]=aid;//将b集合编号改为a集合编号}}}```

优化后的代码:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class Main{static int[] ints;static Set<Integer> set=new HashSet<Integer>();public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();ints = new int[m * n];for (int i = 0; i < ints.length; i++) {ints[i] = i;}//进行k次合并int k = scanner.nextInt();for (int i = 0; i < k; i++) {int a = scanner.nextInt();int b = scanner.nextInt();//数组从0开始故减去1union(a - 1, b - 1);}show();System.out.println(set.size());}//合并private static void union(int a, int b) {int aid=find(a);int bid=find(b);ints[bid]=aid;}//查找根节点private static int find(int i) {while (i != ints[i]){i=ints[i];}return i;}//将结果添加入集合private static void show() {for (int i = 0; i <ints.length ; i++) {/* if (i%4==0) System.out.println();System.out.print(find(i)+" ");*/set.add(find(i));}}
}