字母結點型DSU

字母節點型DSU:

Solution:

Use a hashmap to store a mapping between the labels of nodes and the labels of their parent nodes. For each item in this hashmap, the key is the label of one node and the value is the label of its parent node.

Code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DSU {
    private Map<String, String> parent;
    private Map<String, Integer> rank;

    public DSU(String[][] edges) {
        parent = new HashMap<>();
        rank = new HashMap<>();

        for(String[] edge: edges) {
            for(String node: edge) {
                if (!parent.containsKey(node)) {
                    parent.put(node, node);
                    rank.put(node, 0);
                }
            }
        }
    }

    public String find(String s) {
        if(!s.equals(parent.get(s))) {
            String root = find(parent.get(s));
            parent.put(s, root);
        }
        return parent.get(s);
    }

    public void union(String s1, String s2) {
        String s1R = find(s1);
        String s2R = find(s2);

        if(s1R.equals(s2R)) {
            return;
        }else{
            if(rank.get(s1R) < rank.get(s2R)) {
                parent.put(s1R, s2R);
            }if(rank.get(s1R) > rank.get(s2R)) {
                parent.put(s2R, s1R);
            }else{
                parent.put(s2R, s1R);
                rank.put(s1R, rank.get(s1R)+1);
            }
        }
    }

    public int getConnectedPart() {
        int connectedPart = 0;
        for(String key: parent.keySet()) {
            if(parent.get(key).equals(key)) {
                connectedPart += 1;
            }
        }
        return connectedPart;
    }

    public static void main(String[] args) {
        String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "C"}, {"D", "E"}};
        DSU dsu = new DSU(edges);

        for(String[] edge: edges) {
            dsu.union(edge[0], edge[1]);
        }

        int connectedPart = dsu.getConnectedPart();
        System.out.println(connectedPart); // 2
    }

}