方法一,
结果超时;
思路是使用深搜,使每一个节点为出发点,将当前节点走过的地方标记,之后不用走,走完后总数量加一。
import java.util.Scanner; public class 和根植物 { /** * @param args */ public static int arr[][]=null; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); arr=new int[n*m+1][n*m+1]; int t=sc.nextInt(); while (t-->0) { int x=sc.nextInt(); int y=sc.nextInt(); arr[y][x]=arr[x][y]=1;//表示有路可走 } //数据初始化 for (int i = 0; i < arr.length; i++) { arr[i][0]=i; arr[0][i]=i; } int countBox=0;//结果 //countBox+单根的连根情况 for (int k = 1; k <=n*m; k++) { boolean bo=true; for (int i = 1; i <=n*m; i++) { if (arr[k][i]==1 || arr[i][k]==1) { bo=false; break; } } if (bo) { countBox++; } } //开始搜索 for (int i = 1; i <=n*m; i++) { for (int j = 1; j <=n*m; j++) { if (arr[i][j]==1) { countBox++; dfs(i); } } } System.out.println(countBox); } public static void dfs(int step) { for (int i = 1; i <arr.length; i++) { if (arr[step][i]==1) { arr[step][i]=arr[i][step]=-1; dfs(i); } } } }
方法二:并查集
并查集有两个关键方法,查找、合并,分别是getF(),merge();
getF():查找当前元素的父元素。
merge():合并节点,使两个节点共同属于同一根节点。
import java.util.Scanner; public class 合根植物_并查集 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int count=0; int f[]=new int[n*m+1]; //数据初始化 for (int i = 1; i < f.length; i++) { f[i]=i; } //输入 int k=sc.nextInt(); while (k-->0) { int a=sc.nextInt(); int b=sc.nextInt(); merge(f, a, b);//合并a与b植物 } //找出合根植物的数量 for (int i = 1; i < f.length; i++) { if (f[i]==i) { count++; } } System.out.println(count); } //getF ,获取根节点 public static int getF(int f[],int v) { if (f[v]==v) { return v; }else { f[v]=getF(f, f[v]); return f[v]; } } //merge,合并节点 public static void merge(int f[],int v,int u) { int t1=getF(f, v); int t2=getF(f, u); if (t1!=t2) { f[t2]=t1; } } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:521 |
Hello, world! (C++代码)浏览:1752 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:579 |
蚂蚁感冒 (C语言代码)浏览:784 |
筛排处理 (C语言代码)浏览:799 |
printf基础练习 (C语言代码)浏览:1855 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:614 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:610 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:495 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:618 |