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

解题思路:

    总的根数为m*n个，通过并查集将能连起来的点都连起来，同时每连一次只要没有形成闭合的环，根的总数就会少一个。python实现超时了，同样的思路用java实现AC了。

python参考代码:

m,n = map(int,input().split())
k = int(input())
parent = [-1 for _ in range(m*n+1)] #初始化各个节点的父节点为-1，开始谁都是根节点
rank = [0 for _ in range(m*n+1)]    #记录树的长度
num = n*m
def find(x,parent):     #查找根节点
    if parent[x]==-1:
        return x
    else:
        while parent[x] != -1:
            x = parent[x]
    return x
for _ in range(k):
    x,y = map(int,input().split())
    xRoot = find(x,parent)
    yRoot = find(y,parent)
    if xRoot!= yRoot:   #合并
        if rank[xRoot]>rank[yRoot]:
            parent[yRoot] = xRoot
        elif rank[yRoot] > rank[xRoot]:
            parent[xRoot] = yRoot
        elif rank[xRoot] == rank[yRoot]:
            parent[yRoot] = xRoot
        num -= 1
print(num)

java参考代码：

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m,n,k;
		m = scan.nextInt();
		n = scan.nextInt();
		k = scan.nextInt();
		int num = m*n;
		int[] parent = new int[num+1];
		int[] rank = new int[num+1];
		init(parent);
//		System.out.println(parent[1]);
		for (int i = 0; i < k; i++) {
			int x,y,xRoot,yRoot;
			x = scan.nextInt();
			y = scan.nextInt();
			xRoot = find(x,parent);
			yRoot = find(y,parent);
			if(xRoot != yRoot) {
				if (rank[xRoot]>rank[yRoot]) {
					parent[yRoot] = xRoot;
				}else if(rank[yRoot]>rank[xRoot]){
					parent[xRoot] = yRoot;
				}else if(rank[yRoot]==rank[xRoot]) {
					parent[yRoot] = xRoot;
				}
				num--;
			}
		}
		System.out.println(num);
		
	}
	/**
	 * 初始化压缩数组
	 * @param parent
	 */
	public static void init(int[] parent) {
		for (int i = 0; i < parent.length; i++) {
			parent[i] = -1;
		}
	}
	/**
	 * 查找根节点
	 * @param x
	 * @param parent
	 * @return
	 */
	public static int find(int x,int[] parent) {
		if(parent[x] == -1) {
			return x;
		}else {
			while(parent[x] != -1) {
				x = parent[x];
			}
		}
		return x;
	}

}