合根植物（JAVA）

题目

w 星球的一个种植园，被分成 m×n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

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

输入描述
第一行，两个整数 m,n，用空格分开，表示格子的行数、列数（1≤m,n≤1000）。

接下来一行，一个整数 k (0≤k≤10^5 )，表示下面还有 k 行数据。

接下来 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

样例说明

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

代码：

 
import java.util.Scanner;
 
public class Main {
   static int n,m;       //定义行列
   static int []pre=new int[10000001];    //pre数组存储根（上级）
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        int k;
        k=sc.nextInt();
        int [][] arr=new int[k][2];
        for (int i=0;i<k;i++){
            for (int j=0;j<2;j++) {
                arr[i][j]=sc.nextInt();
            }
        }                                  //输入
        int x=n*m;
        for (int i=1;i<x+1;i++){
            pre[i]=i;                    //初始化pre数组（所有植物的根都为本身）
        }
        for (int i=0;i<k;i++){
            join(arr[i][0],arr[i][1]);    //合并根
        }
        boolean [] a=new boolean[x+1];    
        for (int i=0;i<x+1;i++){
            a[i]=false;
        }
        for (int i=1;i<x+1;i++){
            a[find(i)]=true;        
        }
        int sum=0;
        for (int i=1;i<x+1;i++){
            if (a[i]){
                sum++;            //统计根的个数，进而得到有多少棵植物。
            }
        }
        System.out.println(sum);
 
 
    }
 
 
 
    public static Integer find(int x){      //查找植物的根
        if (x==pre[x]){
            return x;
        }
        return pre[x]=find(pre[x]);
    }
 
 
 
    public static void join(int x,int y){    //如果两个植物的根不相同，那么前一个植物的根变为后一个植物。
        x=find(x);
        y=find(y);
        if (x!=y){
            pre[x]=y;
        }
    }
}

思路：

运用并查集的思想，将所有的合根植物的根变为一个，最终根的数量就是植物的数量。