# union find

## OO + path compression

class UnionFind:
    def __init__(self):
        self.group_id_dict = {}  # node_id as key; group_id as value.

    def find(self, node_id):
        #if node_id not in self.group_id_dict:
        #    self.group_id_dict[node_id] = node_id
        #group_id = self.group_id_dict[node_id]
        group_id = self.group_id_dict.setdefault(node_id, node_id)

        # Path compressio, recursively updating for all nodes on path.
        # This will flatten the tree.
        if group_id != node_id:
            new_group_id = self.find(group_id)
            self.group_id_dict[node_id] = new_group_id

        return self.group_id_dict[node_id]

    def union(self, x, y):
        #x_group_id = self.find(x)
        #y_group_id = self.find(y)
        #
        #if x_group_id != y_group_id:
        #    self.group_id_dict[x_group_id] = y_group_id
        self.group_id_dict[self.find(x)] = self.find(y)
        # Merge the two group by letting the representative of a group be the
        # representative of the other


union_find = UnionFind()

for x, y in pairs:
    union_find.union(x, y)

## the same, OO + path compression

class UnionFind:
    def __init__(self):
        # nid: node id
        # gid: groud id
        self.nid2gid = {}
    def find(self, nid):
        gid = self.nid2gid.setdefault(nid, nid)
        if gid!=nid:
            self.nid2gid[nid] = self.find(gid)
        return self.nid2gid[nid]  # same as gid
    def union(self, nid_1, nid_2):
        self.nid2gid[self.find(nid_1)] = self.find(nid_2)

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        uf = UnionFind()
        inequality = []
        for text in equations:
            if '==' in text:
                a, b = text.split('==')
                uf.union(a, b)
            else:
                a, b = text.split('!=')
                inequality.append([a, b])
        for a, b in inequality:
            if uf.find(a) == uf.find(b):
                return False
        return True

## nice ref, path compression when find(), union() by rank

https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/