并查集学习笔记

并查集

1. 有若干个样本a、b、c、d…类型假设是V
2. 在并查集中一开始认为每个样本都在单独的集合里
3. 用户可以在任何时候调用如下方法: boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合 void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合
4. isSameSet和union方法的代价越低越好

代码语言：javascript复制

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class UnionFind {
    public static class Node<V> {
        V value;
        public Node(V v) {
            value = v;
        }
    }

    public static class UnionSet<V> {
        //V->节点表
        public HashMap<V, Node<V>> nodes;
        //记录节点父节点
        public HashMap<Node<V>, Node<V>> parents;
        //当一个点是代表点才记录
        public HashMap<Node<V>, Integer> sizeMap;
        //建立并查集
        public UnionSet(List<V> values) {
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        /**查找父节点，用来判断是否是相同集合
         * 建立一个栈来存放路径
         */
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            //当前节点与其父节点不同时，将当前节点压入栈中
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            //栈不为空，弹出栈顶元素即为父节点
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            //返回父节点
            return cur;
        }

        public boolean isSameSet(V a, V b) {
            //判断输入的两个元素是否为整个集合内的元素
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return false;
            }
            //根据父节点判断是否为同一集合
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return;
            }
            //找到对应元素父节点，将小集合贴到大集合后面
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize >= bSetSize) {
                    parents.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize   bSetSize);
                    sizeMap.remove(bHead);
                } else {
                    parents.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize   bSetSize);
                    sizeMap.remove(aHead);
                }
            }
        }
    }
}

并查集的一道小问题

有某网站的账户实例包含三个ID，身份证ID、网站ID、github ID，如果两个用户实例中的任意一个ID相同则判断为同一用户，请问最终判断完后，还剩多少用户

代码语言：javascript复制

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class MergeUsers {

	public static class Node<V> {
		V value;

		public Node(V v) {
			value = v;
		}
	}

	public static class UnionSet<V> {
		public HashMap<V, Node<V>> nodes;
		public HashMap<Node<V>, Node<V>> parents;
		public HashMap<Node<V>, Integer> sizeMap;

		public UnionSet(List<V> values) {
			for (V cur : values) {
				Node<V> node = new Node<>(cur);
				nodes.put(cur, node);
				parents.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
		public Node<V> findFather(Node<V> cur) {
			Stack<Node<V>> path = new Stack<>();
			while (cur != parents.get(cur)) {
				path.push(cur);
				cur = parents.get(cur);
			}
			// cur头节点
			while (!path.isEmpty()) {
				parents.put(path.pop(), cur);
			}
			return cur;
		}

		public boolean isSameSet(V a, V b) {
			if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return false;
			}
			return findFather(nodes.get(a)) == findFather(nodes.get(b));
		}

		public void union(V a, V b) {
			if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return;
			}
			Node<V> aHead = findFather(nodes.get(a));
			Node<V> bHead = findFather(nodes.get(b));
			if (aHead != bHead) {
				int aSetSize = sizeMap.get(aHead);
				int bSetSize = sizeMap.get(bHead);
				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
				Node<V> small = big == aHead ? bHead : aHead;
				parents.put(small, big);
				sizeMap.put(big, aSetSize   bSetSize);
				sizeMap.remove(small);
			}
		}
		
		//有多少个集合就用多少个用户
		public int getSetNum() {
			return sizeMap.size();
		}
		
	}

	public static class User {
		public String a;
		public String b;
		public String c;

		public User(String a, String b, String c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}

	}

	// 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人
	// 请合并users，返回合并之后的用户数量
	public static int mergeUsers(List<User> users) {
		UnionSet<User> unionFind = new UnionSet<>(users);
		HashMap<String, User> mapA = new HashMap<>();
		HashMap<String, User> mapB = new HashMap<>();
		HashMap<String, User> mapC = new HashMap<>();
		//判断集合中是否已经存在相同字段，有就合并
		for(User user : users) { 
			if(mapA.containsKey(user.a)) {
				unionFind.union(user, mapA.get(user.a));
			}else {
				mapA.put(user.a, user);
			}
			if(mapB.containsKey(user.b)) {
				unionFind.union(user, mapB.get(user.b));
			}else {
				mapB.put(user.b, user); 
			}
			if(mapC.containsKey(user.c)) {
				unionFind.union(user, mapC.get(user.c));
			}else {
				mapC.put(user.c, user);
			}
		}
		// 向并查集询问，合并之后，还有多少个集合？
		return unionFind.getSetNum();
	}

}

网站 nodes public 集合 学习笔记

0 人点赞