并查集系列（二）——Union-find with specific canonical element

Union-find with specific canonical element. Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better. For example, if one of the connected components is {1,2,6,9}, then the find() method should return 9 for each of the four elements in the connected components.

问题描述

Union-find with specific canonical element. Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better. For example, if one of the connected components is {1,2,6,9}, then the find() method should return 9 for each of the four elements in the connected components.

思路分析

通过添加一个数组来完成对于每个树最大值进行维护

JAVA代码实现

public class FindMax {
	private  int[] max = new int[10]; // 每个节点对应树的最大值
	private  int[] roots = new int[10]; // 每个点的父节点
	private  int[] points = new int[10]; // 每个点所在树的节点数量

	public FindMax(){
		for (int i = 0; i < roots.length; i++) {
			roots[i] = i;
		}
		for (int i = 0; i < points.length; i++) {
			points[i] = 1;
		}
		for (int i = 0; i < max.length; i++) {
			max[i] = i;
		}
	}

	public  int find(int a){
		return max[root(a)];
	}

	public  void union(int a, int b) {
		int rootA = root(a);
		int rootB = root(b);
		if (root(rootA) != root(rootB)) {
			if (points[rootA] < points[rootB]) {
				roots[rootA] = rootB;
				points[rootB] += points[rootA];
				if(max[rootA]> max[rootB]) max[rootB] = max[rootA];
			}
			if (points[rootB] <= points[rootA]) {
				roots[rootB] = rootA;
				points[rootA] += points[rootB];
				if(max[rootB]> max[rootA]) max[rootA] = max[rootB];
			}
		}
	}

	public  int root(int a) {
		while (roots[a] != a) {
			a = roots[a];
		}
		return a;
	}

	public static void main(String[] args) {
		FindMax find = new FindMax();
		find.union(1, 2);
		find.union(1, 4);
		find.union(4, 6);
		find.union(5, 2);
		System.out.println(find.find(2));
	}

}

运行结果：

6