Python BFS and DFS Solution


  • 0
    C

    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)
    

Log in to reply
 

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