[Python] [Union-Find Set] a little different and clear code, it's worth seeing.


  • 0
    Y

    basic union-find set usage, only one place need explain, if you want know how many tree of this forest, you can count the number of father
    but compress the path to be one. See code:

    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
    
            n = len(M[0])
            fa = list(range(n))
    
            def find(x):
                if fa[x] != x:
                    fa[x] = find(fa[x])
                return fa[x]
    
            def union(x, y):
                fx = find(x)
                fy = find(y)
                if fx != fy:
                    fa[fy] = fx
    
            for i in range(n):
                for j in range(i + 1, n):
                    if M[i][j] == 1:
                        union(i, j)
    
            map(find, range(n))  # important make all child path length = 1 
    
            return len(set(fa))
    

Log in to reply
 

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