Python, Simple Explanation


  • 11

    From some source, we can visit every connected node to it with a simple DFS. As is the case with DFS's, seen will keep track of nodes that have been visited.

    For every node, we can visit every node connected to it with this DFS, and increment our answer as that represents one friend circle (connected component.)

    def findCircleNum(self, A):
        N = len(A)
        seen = set()
        def dfs(node):
            for nei, adj in enumerate(A[node]):
                if adj and nei not in seen:
                    seen.add(nei)
                    dfs(nei)
        
        ans = 0
        for i in xrange(N):
            if i not in seen:
                dfs(i)
                ans += 1
        return ans
    

  • 2

    My version by iteration:

    class Solution(object):
        def findCircleNum(self, M):
            seen = set([])
            res = 0
            for i in range(len(M)):
                if i not in seen:
                    toSee = [i]
                    while len(toSee):
                        cur = toSee.pop()
                        if cur not in seen:
                            seen.add(cur)
                            toSee = [j for j,v in enumerate(M[cur]) if v and j not in seen] + toSee
                    res += 1
            return res

  • 0
    Y

    [[0,1,0],[1,1,0],[1,1,0]]
    this test case doesn't work


  • 1

    @yiz202 your test case isn't valid.

    M[i][i] = 1 for all students.
    If M[i][j] = 1, then M[j][i] = 1.

  • 1
    I

    Similar DFS solution, which uses a queue and costs 55ms.

    class Solution(object):
        def findCircleNum(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            if len(M) == 0: return 0
            s = set(range(len(M)))
            count = 0
            q = []
            while True:
                if len(q) == 0:
                    if s:
                        q.append(s.pop())
                        count += 1
                    else:
                        break
                item, q = q[0], q[1:]
                for i in list(s):
                    if M[item][i]:
                        q.append(i)
                        s.remove(i)
            return count
    

  • 0
    H

    @IvesWang If you use Python's collections.dequeue instead of a list, you may have better performance with item = q.popleft() instead of item, q = q[0], q[1:] which recreates the list.


  • 0
    I

    @hk3380 I will try it. Thank u for printing out.


  • 0
    A

    @awice can you explain the dfs part? what is node?


Log in to reply
 

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