Java-并查集

àì夳堔傛蜴生んèń 2023-10-09 18:12 15阅读 0赞

假设最开始有这样一个坨元素 a b c d e f g h

最开始这些元素各自为一个集合\{a\} \{b\} \{c\} \{d\} \{e\} \{f\} \{g\}

并查集的作用是把这些元素链接起来

假如要把b和a链接起来 就变成了\{a,b\}\{c\} \{d\} \{e\} \{f\} \{g\}

再把c和b链接起来呢(与a和c连接起来等效哦)? \{a,b,c\}\{d\} \{e\} \{f\} \{g\}

#### 点定义 ####

class Node{
        int value;
    }

### 并查集定义 ###

#### 并查集中的成员变量 ####

class Unionfind{
    	HashMap<Integer,Node> map = new HashMap<Integer, Node>();
    	HashMap<Node, Node> parents = new HashMap<Node, Node>();
    	HashMap<Node, Integer> size = new HashMap<Node, Integer>();
    }

#### 并查集中的成员方法 ####

1.取得父节点

public Node getfather(Node node) {
    		Stack<Node> stack = new Stack<Node>();
    		while(parents.get(node)!=node) {
    			stack.push(node);
    			node = parents.get(node);
    		}
    		while(!stack.isEmpty()) {
    			parents.put(stack.pop(), node);
    		}
    		return node;
    	}

如果只是单纯的取得父节点只需要

public Node getfather(Node node) {
    		while(parents.get(node)!=node) {
    			node = parents.get(node);
    		}
    		return node;
    	}

我们再此基础上做了一个优化,把这条路径上的每一个节点都直接连接到父节点上,下次查找的时候就不需要再遍历了

2.判断两个点是否在同一个集中

public boolean issame(Node node1,Node node2) {
    		if (!map.containsKey(node1) || !map.containsKey(node2)) {
    			return false;
    		}
    		return parents.get(node1)==parents.get(node2);
    	}

3.连接两个点

两个点连接 那么就相当于两个点所在的集连接了

我们选择把小的集接在大的集上面

记得把小的集的size消除掉

看一个集的大小 就是这个集的头元素对应的size

如果他们是同一个头的话 那么就会把这个头的size remove掉 所以要加一个if

public void union(Node node1,Node node2) {
    		if (!map.containsKey(node1) || !map.containsKey(node2)) {
    			return;
    		}
    		Node head1 = getfather(node1);
    		Node head2 = getfather(node2);
    		if (head1 != head2) {
    		Node big = size.get(head1)>size.get(head2)?node1:node2;
    		Node small = big==head1?head2:head1;
    		parents.put(small,big);
    		size.put(big, size.get(head1)+size.get(head2));
    		size.remove(small);
    		}
    	}