<jupyter_start><jupyter_text>**684. Redundant Connection**<jupyter_code>def findRedundantConnection(edges):
    p = [0]*(len(edges)+1)
    s = [1]*(len(edges)+1)
    
    # path compression during find
    def find(u):
        while p[u] != u:
            p[u] = p[p[u]]
            u = p[u]
        return u
    
    for u, v in edges:
        if p[u] == 0:
            p[u] = u
        if p[v] == 0:
            p[v] = v
        pu, pv = find(u), find(v)
        if pu == pv:
            return [u, v]
        
        # union by rank, make sure pv is lower rank
        # link v's parent node to u's, increase size
        if s[pv] > s[pu]:
            u, v = v, u
        p[pv] = pu
        s[pu] += s[pv]
        
    return []
edges = [[1,2], [1,3], [2,3]]
findRedundantConnection(edges)
for u,v in edges:
    print (u,v)<jupyter_output>1 2
1 3
2 3<jupyter_text>**547. Number of Provinces**<jupyter_code>"""
Method 1: DFS
Time complexity: O(n^2)
Space complexity: O(n)
"""
class Solution(object):
    def findCircleNum(M):
        def dfs(M, curr, n):
            for i in range(n):
                if M[curr][i] == 1:
                    M[curr][i] = M[i][curr] = 0
                    dfs(M, i, n)
        
        n = len(M)
        ans = 0
        for i in range(n):
            if M[i][i] == 1:
                ans += 1
                dfs(M, i, n)       
        return ans
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Solution.findCircleNum(isConnected)
"""
Method 2: Union Find

"""
class Solution:
    def findCircleNum(isConnected):
             
        def find(u):
            while u != p[u]:
                p[u] = find(p[u])
                u = p[u]
            return u
                      
        m = len(isConnected)
        p = []
        for i in range(m):
            p.append(i)
        
        for i in range(m):
            for j in range(i, m):
                if i != j and isConnected[i][j] == 1 and find(i) != find(j):
                    p[find(i)] = find(j)
        
        provinces = []
        for n in range(m):
            if p[n] == n:
                provinces.append(n)
        
        return len(provinces)
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Solution.findCircleNum(isConnected)<jupyter_output><empty_output><jupyter_text>**737. Sentence Similarity II**<jupyter_code>class UFS:
    def __init__(self, n):
        self.p = [0]*(n+1)
        self.s = [1]*(n+1)
    def find(self, u):
        while u != self.p[u]:
            self.p[u] = self.p[self.p[u]]
            u = self.p[u]
        return u
    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv: return False
        if s[pu] > s[pv]:
            u, v = v, u
        p[pu] = pv
        s[pv] += s[pu]
        return True
        
class Solution:
    def areSentencesSimilarTwo(words1, words2, pairs):
        
        if len(words1) != len(words2):
            return False
        
        index = {}
        ufs = UFS(2*len(pairs))
        
        for pair in pairs:
            u = Solution.getIndex(pair[0], index, 'True')
            v = Solution.getIndex(pair[1], index, 'True')
            ufs.union(u, v)
        print(index)
        
        for i in range(len(words1)):
            if words1[i] == words2[i]:
                continue
            u, v = getIndex(words1[i], index, 'False'), getIndex(words2[i], index, 'False')
            print(u, v)
            if u < 0 or v < 0:
                return False
            if ufs.find(u) != ufs.find(v):
                return False
        print (index)
        return True
        
    
    def getIndex(word, index, create):
        print(word)
        if word in index:
            return index[word]
        else:
            if create == 'True':
                num = len(index)
                index[word] = num
                return num
            return -1
words1 = ["great","acting","skills"]
words2 = ["fine","painting","talent"]
pairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Solution.areSentencesSimilarTwo(words1,words2,pairs)
def getIndex(word, index, create = 'False'):
    if word in index:
        return index[word]
    else:
        if not create:
            return -1
        num = len(index)
        index[word] = num
        return num

index = {}
for pair in pairs:
    u = getIndex(pair[0], index, 'True')
    v = getIndex(pair[1], index, 'True')
index<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup