Python using stack


  • 0

    Each time stack is empty, we go through every student in the current friend cycle, and we increment ans by 1. Keep doing this until we have no student left in left.

    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            ans = 0
            left = set(range(len(M)))
            while left:
                seen, stack = set(), [left.pop()]
                while stack:
                    x = stack.pop()
                    seen.add(x)
                    stack.extend(j for j, c in enumerate(M[x]) if c \
                                 and j in left and j not in seen)
                left -= seen
                ans += 1
            return ans
    

Log in to reply
 

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