package com.platform.model.vo; import lombok.Data; import java.util.HashMap; import java.util.Map; @Data public class UnionFindVO { private Map parent; private Map rank; public UnionFindVO() { parent = new HashMap<>(); rank = new HashMap<>(); } public void makeSet(String node) { parent.put(node, node); rank.put(node, 0); } public String find(String node) { if (!parent.containsKey(node)) { makeSet(node); } if (!parent.get(node).equals(node)) { parent.put(node, find(parent.get(node))); // 路径压缩 } return parent.get(node); } public void union(String node1, String node2) { String root1 = find(node1); String root2 = find(node2); if (!root1.equals(root2)) { if (rank.get(root1) > rank.get(root2)) { parent.put(root2, root1); } else if (rank.get(root1) < rank.get(root2)) { parent.put(root1, root2); } else { parent.put(root2, root1); rank.put(root1, rank.get(root1) + 1); } } } public Map getParent() { return parent; } }