# Python BFS and DFS Solution

• Both solutions save the friends of each group. The length of the group is the answer.

``````# BFS Solution
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
nums = len(M)
res = []
marked = [False for _ in range(nums)]
for j in range(nums):
if marked[j]:
continue
marked[j] = True
res.append([j])
stack = [j]
while stack:
s = stack.pop(0)
for i in range(nums):
if s != i and M[s][i] == 1 and i not in res[-1]:
marked[i] = True
stack.append(i)
res[-1].append(i)
return len(res)

# DFS Solution
def dfs(self, M, buf, index, visited):
for i in range(len(M)):
if i != index and M[i][index] and not visited[i]:
visited[i] = True
buf.append(i)
buf = self.dfs(M, buf, i, visited)
return buf

def findCircleNum1(self, M):
res = []
visited = [False for _ in range(len(M))]
for i in range(len(M)):
if not visited[i]:
buf = [i]
visited[i] = True
res.append(self.dfs(M, buf, i, visited))
return len(res)
``````

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