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

解题思路:

注意事项:

参考代码:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Main {
	static Map<Integer, UnionNode.Node> pntAndMap = new HashMap<Integer, UnionNode.Node>();
	static Set<UnionNode.Node> nod = new HashSet<UnionNode.Node>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m  = sc.nextInt();
		int n = sc.nextInt();
		int index = 1;
		int[][] a =new int[m+1][n+1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				a[i][j] = index++;
				pntAndMap.put(a[i][j], new UnionNode.Node());
			}
		}
		int k = sc.nextInt();
		for (int i = 0; i < k; i++) {
			UnionNode.Node s = pntAndMap.get(sc.nextInt());
			UnionNode.Node e = pntAndMap.get(sc.nextInt());
			
			if(UnionNode.find(s) != UnionNode.find(e)){
				UnionNode.Union(s, e);
			}
		}
		
		Set<UnionNode.Node> res = new HashSet<>();
		for (int i = 1; i < a.length; i++) {
			for (int j = 1; j < a[i].length; j++) {
				UnionNode.Node node = pntAndMap.get(a[i][j]);
				UnionNode.Node f = UnionNode.find(node);
				res.add(f);
			}
		}
		System.out.println(res.size());
	}
}
class UnionNode{
	
	public static Node find(Node x){
		Node p = x;
		Set<Node> set = new HashSet<>();
		while(p.parent != null){
			set.add(p);
			p = p.parent;
			
		}
		
		for (Node node : set) {
			node.parent = p;
		}
		return p;
	}
	
	public static void Union(Node x, Node y){
		find(y).parent = find(x);
	}
	static class Node{
		public Node parent;
	}
}