蓝桥杯2017年第八届真题-合根植物-题解（Java代码）

方法一，

结果超时；

思路是使用深搜，使每一个节点为出发点，将当前节点走过的地方标记，之后不用走，走完后总数量加一。

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;
		}
	}

}