11.1 题目： 问题描述 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 样例说明 其合根情况参考下图

程序一：（并查集）

我的理解:要想寻找一株合根植物，那么其实就是找连通图，判断两个点是否在连通图中，因此我们可以建立无向图，但是用图的数据结构最大是问题是，算法时效过低，因此我们将这个题目转化为对并查集的操作问题。 构建一个连通图，mat[i]的值是下一个结点的索引位置。当mat[i] = 时代表此时是根节点。

package Mycup; import java.util.Scanner; public class test { static int[] mat = new int[1000001]; public static int find(int x){ //找到当前结点所在的连通图的根节点。返回其索引值。 while(x != test.mat[x]){ x = test.mat[x]; } return x; } public static void liangen(int x,int y){ //如果x在连通图中，y不在，那么根节点被赋值为y，y变为根节点，如果y在连通图中，x不在，那么y还是根节点，但是x加入了该连通图中。 mat[find(x)] = find(y); } public static void main(String[] args){ int count =0; Scanner in = new Scanner(System.in); int row = in.nextInt(); int clo = in.nextInt(); int k = in.nextInt(); for (int i =0;i<=row*clo;i++){ mat[i] = i; } for (int i =0;i<k;i++){ int x1 = in.nextInt(); int x2 = in.nextInt(); //获取连根坐标 test.liangen(x1,x2); } for(int i =1;i<=row*clo;i++){ if(find(i) == i) count += 1; } System.out.print(count); } }

程序二

解法是:如果两个结点在一个连通图中，那么两个结点的值就是一样，且其值代表连通图的序号，因此最后只需将连通图的序号加上单根植物的棵树即结果。

package Mycup; import java.util.Scanner; public class test { static int[] mat = new int[1000001]; static int count =0; public static int find(int x){ while(x != test.mat[x]){ x = test.mat[x]; } return x; } public static void liangen(int x,int y){ //将结点加入到连通图中，如果两个点都不在连通图中，那么新建一个连通图。 if (mat[x] == 0 && mat[y] ==0){ test.count ++; mat[x] = test.count; mat[y] = test.count; } else { if (mat[x] != 0){ mat[y] = mat[x]; } else{ mat[x] = mat[y]; } } } public static void main(String[] args){ Scanner in = new Scanner(System.in); int row = in.nextInt(); int clo = in.nextInt(); int k = in.nextInt(); for (int i =0;i<=row*clo;i++){ mat[i] = 0; } for (int i =0;i<k;i++){ int x1 = in.nextInt(); int x2 = in.nextInt(); //获取连根坐标 test.liangen(x1, x2); } for(int i =1;i<k;i++){ if(mat[i] == 0) count ++; } System.out.print(count); } }