Simple Python DFS


  • 0

    DFS search each friend chain then record all visited friends for each run. Increment counter only if an unvisited friend is discovered, as this indicates the start of a new chain

        def findCircleNum(self, M):
            processed = set()
            cnt = 0
            for r in range(len(M)): 
                if r not in processed:
                    cnt += 1
                    stack = [i for i,v in enumerate(M[r]) if i != r and v == 1]
                    while stack:
                        curr = stack.pop()
                        if curr in processed: continue
                        processed.add(curr)
                        stack.extend([i for i,v in enumerate(M[curr]) if i != r and v == 1])
            return cnt
    

Log in to reply
 

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