并查集学习笔记

发布于

并查集

  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&lt;V&gt; {
    //V-&gt;节点表
    public HashMap&lt;V, Node&lt;V&gt;&gt; nodes;
    //记录节点父节点
    public HashMap&lt;Node&lt;V&gt;, Node&lt;V&gt;&gt; parents;
    //当一个点是代表点才记录
    public HashMap&lt;Node&lt;V&gt;, Integer&gt; sizeMap;
    //建立并查集
    public UnionSet(List&lt;V&gt; values) {
        for (V cur : values) {
            Node&lt;V&gt; node = new Node&lt;&gt;(cur);
            nodes.put(cur, node);
            parents.put(node, node);
            sizeMap.put(node, 1);
        }
    }
    /**查找父节点，用来判断是否是相同集合
     * 建立一个栈来存放路径
     */
    public Node&lt;V&gt; findFather(Node&lt;V&gt; cur) {
        Stack&lt;Node&lt;V&gt;&gt; path = new Stack&lt;&gt;();
        //当前节点与其父节点不同时，将当前节点压入栈中
        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&lt;V&gt; aHead = findFather(nodes.get(a));
        Node&lt;V&gt; bHead = findFather(nodes.get(b));
        if (aHead != bHead) {
            int aSetSize = sizeMap.get(aHead);
            int bSetSize = sizeMap.get(bHead);
            if (aSetSize &gt;= 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&lt;V&gt; {
	V value;

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

public static class UnionSet&lt;V&gt; {
	public HashMap&lt;V, Node&lt;V&gt;&gt; nodes;
	public HashMap&lt;Node&lt;V&gt;, Node&lt;V&gt;&gt; parents;
	public HashMap&lt;Node&lt;V&gt;, Integer&gt; sizeMap;

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

	// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
	public Node&lt;V&gt; findFather(Node&lt;V&gt; cur) {
		Stack&lt;Node&lt;V&gt;&gt; path = new Stack&lt;&gt;();
		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&lt;V&gt; aHead = findFather(nodes.get(a));
		Node&lt;V&gt; bHead = findFather(nodes.get(b));
		if (aHead != bHead) {
			int aSetSize = sizeMap.get(aHead);
			int bSetSize = sizeMap.get(bHead);
			Node&lt;V&gt; big = aSetSize &gt;= bSetSize ? aHead : bHead;
			Node&lt;V&gt; 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&lt;User&gt; users) {
	UnionSet&lt;User&gt; unionFind = new UnionSet&lt;&gt;(users);
	HashMap&lt;String, User&gt; mapA = new HashMap&lt;&gt;();
	HashMap&lt;String, User&gt; mapB = new HashMap&lt;&gt;();
	HashMap&lt;String, User&gt; mapC = new HashMap&lt;&gt;();
	//判断集合中是否已经存在相同字段，有就合并
	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#集合#学习笔记