LintCodeBook/DataStructure/Union-Find.md at master · rwang23/LintCodeBook

##Union Find

###Basic Java Model 优化前合并与查找时间复杂度都是O(n) Compressed path优化后都是O(1) union find不支持删除操作

###Implementation

	class UnionFind{
		/*
		用数组或者hashmap都可以
		 */
		HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
		UnionFind(HashSet<Integer> hashSet){
			for(Integer now : hashSet) {
				hashmap.put(now, now);
			}
		}
        int find(int x){
	     /*
		当没找到自己是根节点的时候,就继续深度遍历进入曾祖父找,直到找到最后的根节点
		 */
        	int parent =  hashmap.get(x);
        	while(parent!=hashmap.get(parent)) {
        		parent = hashmap.get(parent);
        	}
        	return parent;
        }
        int compressed_find(int x){
        	int parent =  hashmap.get(x);
        	while(parent!=hashmap.get(parent)) {
        		parent = hashmap.get(parent);
        	}
        	int temp = -1;
        	int fa = hashmap.get(x);
        	while(fa!=hashmap.get(fa)) {
        		temp = hashmap.get(fa);
        		hashmap.put(fa, parent) ;
        		fa = temp;
        	}
        	return parent;

        }

        void union(int x, int y){
        	int root_x = find(x);
        	int root_y = find(y);
        	if(root_x != root_y) {
        		hashmap.put(root_x, root_y);
        	}
        }
	}