Python union find, 85ms.


  • 0
    B
    class Solution(object):
        def find(self, i):
            v = self.dic[i] 
            if v == i: #the root
                return i
            else: 
                r = self.find(v) #find root type, collapse route
                self.dic[i] = r
                return r
            
        def union(self, i, j): #union
            if self.find(i) != self.find(j):#union two different types, just union two roots
                self.dic[self.dic[i]] = self.dic[j]
                
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            self.dic = {} #k:friend_id,v:type
            for i in range(len(M)):
                self.dic[i] = i #init with different types, all is root.
            
            for i,l in enumerate(M):
                j = i + 1 #the left top half of matrix would be enough
                while j < len(M):
                    if l[j] == 1:
                        self.union(i, j) 
                    j += 1
            s = set()
            for i in range(len(M)): #find all types
                s.add(self.find(i))
            return len(s)
                    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.