Friend Circles – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Friend Circles – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object): def findCircleNum(self, M): """ :type M: List[List[int]] :rtype: int """ # because visited = [0] * len(M) count = 0 for i in range(len(M)): if visited[i] == 0: self.dfs(M, visited, i) count += 1 return count def dfs(self, M, visited, i): for j in range(len(M)): if M[i][j] == 1 and visited[j] == 0: visited[j] = 1 self.dfs(M, visited, j) # def findCircleNum(self, M): # # BFS # visited = [0] * len(M) # count = 0 # queue = [] # for i in range(len(M)): # if visited[i] == 0: # queue.append(i) # while queue: # curr = queue.pop(0) # visited[curr] = 1 # for j in range(len(M)): # if M[curr][j] == 1 and visited[j] == 0: # queue.append(j) # count += 1 # return count # def findCircleNum(self, M): # # Union Find # union = Union() # for i in range(len(M)): # union.add(i) # for i in range(len(M)): # for j in range(i + 1, len(M)): # if M[i][j] == 1: # union.union(i, j) # return union.count # class Union(object): # """ # weighted quick union find # """ # def __init__(self): # # both dic and list is fine # self.id = {} # self.sz = {} # self.count = 0 # def count(self): # return self.count # def connected(self, p, q): # return self.find(p) == self.find(q) # def add(self, p): # # init # self.id[p] = p # self.sz[p] = 1 # self.count += 1 # def find(self, p): # """ # find root of p, and compress path # """ # while p != self.id[p]: # self.id[p] = self.id[self.id[p]] # p = self.id[p] # return p # def union(self, p, q): # """ # connect p and q # """ # i, j = self.find(p), self.find(q) # if i == j: # return # if self.sz[i] > self.sz[j]: # i, j = j, i # self.id[i] = j # self.sz[j] += self.sz[i] # self.count -= 1