DFS solution in Python


  • 0
    A
    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            # pretty much finding each connected graph
            connected_components = 0
            visited = [False for i in range(len(M))]
            
            def dfs(i):
                visited[i] = True
                neighbors = M[i]
                for j in range(len(neighbors)):
                    if M[i][j]==1 and visited[j]==False:
                        dfs(j)
            
            for i in range(len(M)):
                if not visited[i]:
                    connected_components += 1
                    # EXPLORE
                    dfs(i)
    
            return connected_components
    

Log in to reply
 

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