蓝桥杯Java-合根植物----------并查集算法

Bertha 。 2022-03-06 05:14 179阅读 0赞

> 今天做蓝桥杯赛题时遇到一道题“合根植物”，用直接递归啊，蛮力法都不好弄。后来看了网上的答案，才恍然大悟，其实就是聚类问题，将有关系的一群东西化为一类，就像各个家族一样，每个人都有一个根节点。

感谢博主的分享，原文地址：[https://blog.csdn.net/striner/article/details/79800433][https_blog.csdn.net_striner_article_details_79800433]

### 题目描述: ###

w[星球][Link 1]的一个种植园，被分成 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  
  
样例输出：

### 解题思路: ###

并查集解题.

总数减掉合并根数便为合根植物的根数.

### 代码实现: ###

import java.util.Scanner; 
       
       public class Main { 
       static int[] tb; //整棵树 
       static int num; //合并数 
       public static void main(String[] args) { 
       Scanner input = new Scanner(System.in); 
       String[] ss = input.nextLine().trim().split( " +"); //根据一个或者多个空格分割 
       
       int M = Integer.parseInt(ss[ 0]); 
       int N = Integer.parseInt(ss[ 1]); 
       
       tb = new int[M*N + 1]; //整棵树 0不存 
       int k = Integer.parseInt(input.nextLine().trim()); //有k条连通数据 
       for ( int i = 0; i < k; i++) { 
       ss = input.nextLine().trim().split( " +"); 
       
       //ss[0] ss[1] 表示ss[0]和ss[1]连 
       fun(Integer.parseInt(ss[ 0]), Integer.parseInt(ss[ 1])); 
       } 
       
       System.out.println(M*N - num); //总数减掉有合并数便为合根植物的根数 
       } 
       
       //a与b连通 
       public static void fun(int a, int b) { 
       
       int ra = find(a); //查询a的父节点 用祖先的号代表整个家族 
       int rb = find(b); 
       
       if (ra == rb) return; //若两树的根节点相同则表示本身就为一颗合并数 
       
       union(ra, rb); //合并ra,rb 
       num++; 
       } 
       public static void union(int ra, int rb) { 
       
       tb[ra] = rb; 
       } 
       public static int find(int x) { //查找其父节点 
       
       if(tb[x] == 0) return x; 
       return tb[x] = find(tb[x]); //并查集 
       } 
       }

### 运行调试: ###

![SouthEast][]

[https_blog.csdn.net_striner_article_details_79800433]: https://blog.csdn.net/striner/article/details/79800433
[Link 1]: https://www.baidu.com/s?wd=%E6%98%9F%E7%90%83&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[SouthEast]: /images/20220306/94fac8fb2b754c2ead7efbc9ee385b51.png