python dfs iter version


  • 1
    Z

    recursion version is easier to understand, but the iterate version shows up in my mind firstly.

    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            circle = 0
            n = len(M)
            for i in xrange(n):
                if M[i][i] != 1:
                    continue
                friends = [i]
                while friends:
                    f = friends.pop()
                    if M[f][f] == 0:
                        continue
                    M[f][f] = 0
                    for j in xrange(n):
                        if M[f][j] == 1 and M[j][j] == 1:
                            friends.append(j)
                circle += 1
            return circle
    

    other people have already posted recursion solutions, but here I still paste mine:

    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            def dfs(node):
                visited.add(node)
                for friend in xrange(len(M)):
                    if M[node][friend] and friend not in visited:
                        dfs(friend)
    
            circle = 0
            visited = set()
            for node in xrange(len(M)):
                if node not in visited:
                    dfs(node)
                    circle += 1
            return circle
    

Log in to reply
 

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