Union and Find (Disjoint Set Union)

Simple version:

(1) (V)

class DSU:
    def __init__(self, N):
        self.par = range(N)

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])    ## path compression
        return self.par[x]

    def union(self, x, y):
        self.par[self.find(x)] = self.find(y)

(2)

        parent = {}
        def find(word):
            if word not in parent or word == parent[word]:
                return word

            return find(parent[word])

        def union(word1, word2):            
            x = find(word1)
            y = find(word2)

            if x != y: 
                parent[x] = y

Improved Version:

path compression + union-by-rank

class Union(object):
    def __init__(self):
        self.id = {}
        self.weighted = {}

    def add(self, i):
        self.id[i] = i
        self.weighted[i] = 1


    def find(self, i):
        if i not in self.id:
            return ""

        while self.id[i] != i:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]

        return i

    def unite(self, i, j):
        rooti = self.find(i)
        rootj = self.find(j)

        if  rooti == rootj:
            return

        if self.weighted[rooti] > self.weighted[rootj]:
            self.id[rootj] = rooti
            self.weighted[rooti] += 1
        else:
            self.id[rooti] = rootj
            self.weighted[rootj] += 1

Time Complexity

#737 Sentence Similarity

class Solution(object):
    def areSentencesSimilarTwo(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        if len(words1) != len(words2):
            return False

        parent = {}
        def find(word):
            if word not in parent or word == parent[word]:
                return word
            return find(parent[word])

        def union(word1, word2):
            x = find(word1)
            y = find(word2)

            if x != y:
                parent[x] = y


        for pair in pairs:
            union(pair[0], pair[1])

        for i in range(len(words1)):

            if (words1[i] != words2[i]) and (find(words1[i]) != find(words2[i])):
                return False

        return True

#721 Account Merge

class Solution(object):
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """

        #email_to_index = {} # index to email
        parent = {}
        email_to_name = {}
        idx = 0

        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)


        for a in accounts:
            name = a[0]
            for email in a[1:]:
                if email not in parent:
                    parent[email] = email
                email_to_name[email] = name
                union(a[1], email)

        graph = collections.defaultdict(list)

        for key in parent.keys():
            graph[find(key)].append(key)

        res = []
        for i in graph:
            res.append([email_to_name[i]] + sorted(graph[i]))

        return res