[数据结构与算法]并查集结构

并查集结构实现

并查集的 $union$ 操作与 $isSameSet$ 操作都是 $O(1)$ （在操作次数比较多，趋近或者超过数据规模大小的时候）。

	public static class Element<K>{
		public K key;
		public Element(K key) {
			this.key=key;
		}
	}
	public static class UnionFindSet<K>{
		public HashMap<K,Element<K>>keyMap=new HashMap<>();
		public HashMap<Element<K>,Integer>sizeMap=new HashMap<>();
		public HashMap<Element<K>,Element<K>>fatherMap=new HashMap<>();
		public UnionFindSet(List<K> m) {
			for(K key:m) {
				Element e=new Element<>(key);
				keyMap.put(key, e);
				sizeMap.put(e, 1);
				fatherMap.put(e, e);
			}
		}
		public Element<K> findHead(K key){
			if(!keyMap.containsKey(key))return null;
			Element e=keyMap.get(key);
			Stack<Element<K>>st=new Stack<>();
			Element cur=e;
			while(fatherMap.get(cur)!=cur) {
				st.push(cur);
				cur=fatherMap.get(cur);
			}
			while(!st.isEmpty()) {
				fatherMap.put(st.pop(), cur);
			}
			return cur;
		}
		public void union(K k1,K k2) {
			Element<K>h1=findHead(k1);
			Element<K>h2=findHead(k2);
			if(h1==h2)return;
			Element<K>big=sizeMap.get(h1)>sizeMap.get(h2)?h1:h2;
			Element<K>small=sizeMap.get(h1)>sizeMap.get(h2)?h2:h1;
			fatherMap.put(small, big);
			sizeMap.put(big, sizeMap.get(big)+sizeMap.get(small));
			sizeMap.remove(small);
		}
		public boolean isSameSet(K k1,K k2) {
			Element<K>h1=findHead(k1);
			Element<K>h2=findHead(k2);
			return h1==h2;
		}
		
	}

并查集题目

岛问题

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public static class Element<K>{
		public K key;
		public Element(K key) {
			this.key=key;
		}
	}
	public static class UnionFindSet<K>{
		public HashMap<K,Element<K>>keyMap=new HashMap<>();
		public HashMap<Element<K>,Integer>sizeMap=new HashMap<>();
		public HashMap<Element<K>,Element<K>>fatherMap=new HashMap<>();
		public UnionFindSet(List<K> m) {
			for(K key:m) {
				Element e=new Element<>(key);
				keyMap.put(key, e);
				sizeMap.put(e, 1);
				fatherMap.put(e, e);
			}
		}
		public Element<K> findHead(K key){
			if(!keyMap.containsKey(key))return null;
			Element e=keyMap.get(key);
			Stack<Element<K>>st=new Stack<>();
			Element cur=e;
			while(fatherMap.get(cur)!=cur) {
				st.push(cur);
				cur=fatherMap.get(cur);
			}
			while(!st.isEmpty()) {
				fatherMap.put(st.pop(), cur);
			}
			return cur;
		}
		public void union(K k1,K k2) {
			Element<K>h1=findHead(k1);
			Element<K>h2=findHead(k2);
			if(h1==h2)return;
			Element<K>big=sizeMap.get(h1)>sizeMap.get(h2)?h1:h2;
			Element<K>small=sizeMap.get(h1)>sizeMap.get(h2)?h2:h1;
			fatherMap.put(small, big);
			sizeMap.put(big, sizeMap.get(big)+sizeMap.get(small));
			sizeMap.remove(small);
		}
		public boolean isSameSet(K k1,K k2) {
			Element<K>h1=findHead(k1);
			Element<K>h2=findHead(k2);
			return h1==h2;
		}
		
	}
    public int solve (char[][] grid) {
        // write code here
        List<String>list=new ArrayList<>();
		for(int row=0;row<grid.length;++row) {
			for(int col=0;col<grid[0].length;++col) {
				if(grid[row][col]=='1') {
					list.add(row+"_"+col);
				}
			}
		}
		UnionFindSet<String>set=new UnionFindSet<>(list);
		for(int row=0;row<grid.length;++row) {
			for(int col=0;col<grid[0].length;++col) {
				if(grid[row][col]=='1') {
					if(row-1>=0&&grid[row-1][col]=='1') {
						set.union(row+"_"+col,row-1+"_"+col);
					}
					if(col-1>=0&&grid[row][col-1]=='1') {
						set.union(row+"_"+col,row+"_"+(col-1));
					}
				}
			}
		}
		return set.sizeMap.size();
    }
}