试题 历届试题 合根植物

问题描述 w星球的一个种植园，被分成mn个小格子（东西方向m行，南北方向n列），每个格子里种了一株合根植物，这种植物有个特点，它的根可能会沿着南北或东西方向延伸，从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？ import Java.util.Scanner; public class Main{ static int father[]=null; public static void main(String[] args){ Scanner s=new Scanner(System.in); int m=s.nextInt(); int n=s.nextInt(); int k=s.nextInt(); father = new int[mn+1]; for(int i=1;i<=mn;i++){ father[i]=i; } for(int i=0;i<k;i++）{ int a=s.nextInt(); int b=s.nextInt(); join(a,b); } int cnt=0; for(int i=1;i<=mn;i++){ if(father[i]==i){ cnt++; } } System.out.println(cnt); } public static void join(int a,int b){ if(getTop(a)!=getTop(b)){ father[getTop(a)]=getTop(b); } } public static int getTop(int a){ if(father[a]==a){ return a; }else{ father[a]=getTop(father[a]); return father[a]; } } }