Graph: Linked List Representation of a disjoint‐set - rFronteddu/general_wiki GitHub Wiki

class Node
{
    int data;
    Node next;
    Node representative;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.representative = this;
    }
}

class DisjointedSet 
{
    private Map<Integer, Node> map = new HashMap<>();

    public void makeSet(int data) {
        map.put(data, new Node(data))
    }

    public int findSet(int data) {
        return findSet(map.get(data)).data;
    }

    private Node findSet(Node node) {
        if(node.representative == node) {
            return node;
        }
        // path compression
        node.representative = findSet(node.representative); 
        return node.representative;
    }

    public void union(int data1, int data2) {
        Node n1 = map.get(data1);
        Node n2 = map.get(data2);

        Node rep1 = findSet(node1);
        Node rep2 = findSet(node2);

        if(rep1 == rep2) {
            return; // already in same set
        }

        // merge the two lists by attaching one to the other
        Node tmp = rep1;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = rep2;

        // update representatives for all the nodes in the merged list
        tmp = rep2;
        while (tmp != null) {
            tmp.representative = rep1;
            tmp = tmp.next;
        }
    }
}