广州营销型网站建设怎么样,佛山智唯网站建设,宁夏建设局官方网站,开网店需要投资多少钱问题描述w星球的一个种植园#xff0c;被分成 m * n 个小格子#xff08;东西方向m行#xff0c;南北方向n列#xff09;。每个格子里种了一株合根植物。这种植物有个特点#xff0c;它的根可能会沿着南北或东西方向伸展#xff0c;从而与另一个格子的植物合成为一体。如…问题描述w星球的一个种植园被分成 m * n 个小格子东西方向m行南北方向n列。每个格子里种了一株合根植物。 这种植物有个特点它的根可能会沿着南北或东西方向伸展从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象你能说出这个园中一共有多少株合根植物吗输入格式第一行两个整数mn用空格分开表示格子的行数、列数1m,n1000。 接下来一行一个整数k表示下面还有k行数据(0k100000) 接下来k行第行两个整数ab表示编号为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 4162 31 55 94 87 89 1010 1111 1210 1412 1614 1817 1815 1919 209 1313 17样例输出5样例说明其合根情况参考下图采用并查集的方法
import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
public class Main { static int []head; public static void main(String[] args) { //并查集 Scanner snew Scanner(System.in); int ms.nextInt(); int ns.nextInt(); int ks.nextInt(); headnew int [m*n]; for(int i0;im*n;i) head[i]i; int a,b; for(int i0;ik;i) { as.nextInt()-1; bs.nextInt()-1; u(a,b); } SetInteger setnew HashSetInteger(); for(int i0;im*n;i) { set.add(f(i)); } System.out.println(set.size()); } private static void u(int a, int b) { if(f(a)f(b)) return; head[f(a)]f(b); } private static int f(int i) { if(head[i]i) return i; return head[i]f(head[i]); } }
