Union Find Easy Understanding Solution


  • 0
    S
    def findCircleNum(self, M):
    	"""
    	:type M: List[List[int]]
    	:rtype: int
    	"""
    	if not M:
    		return 0
    	N = len(M)
    	root = [-1 for i in range(N)]
    	neighbors = [[] for i in range(N)]
    	def find_root(i):
    		if root[i]==-1:
    			return i
    		else:
    			return find_root(root[i])
    	def union(x,y):
    		x_set = find_root(x)
    		y_set = find_root(y)
    		root[x_set] = y_set
    	for i in range(0,N):
    		for j in range(i+1,N):
    			if M[i][j]==1:
    				x = find_root(i)
    				y = find_root(j)
    				if x!=y:
    					union(x,y)
    	circles = set([])
    	for i in range(N):
    		circles.add(find_root(i))
    	return len(circles)
    

Log in to reply
 

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