Python DFS solution with explanation, beats 97%
In this problem, I first construct a graph with each person as a node and build an edge between two nodes if those two people know each other (they are direct f
In this problem, I first construct a graph with each person as a node and build an edge between two nodes if those two people know each other (they are direct friends). Since the matrix is symmetric, I do not have to read all the values in the matrix but only half of them.\n\n```\nclass Solution:\n    def findCircleNum(self, M: List[List[int]]) -> int:\n        \n        graph = collections.defaultdict(list)\n        \n        if not M:\n            return 0\n        \n        n = len(M)\n        for i in range(n):\n            for j in range(i+1,n):\n                if M[i][j]==1:\n                    graph[i].append(j)\n                    graph[j].append(i)\n        \n        visit = [False]*n\n        \n        def dfs(u):\n            for v in graph[u]:\n                if visit[v] == False:\n                    visit[v] = True\n                    dfs(v)\n        \n        count = 0\n        for i in range(n):\n            if visit[i] == False:\n                count += 1\n                visit[i] = True\n                dfs(i)\n        \n        return count\n```\nTime Complexity: O(n^2). O(n^2) to construct the graph and O(n) to run DFS, so the total is O(n^2).\nSpace Complexity: O(n^2) for the worst case. O(n^2) to store the graph dictionary, if all the nodes are connected, the space is O(n^2). O(n) to store visit list. The space complexity of DFS is the depth of the recursion which is no more than O(n).\n\nSimilar solution without constructing the graph:\n```\n# time: O(n^2)\n# space: O(n) to store visit list\n\nclass Solution:\n    def findCircleNum(self, M: List[List[int]]) -> int:\n       \n        if not M:\n            return 0\n        \n        n = len(M)\n        visit = [False]*n\n        \n        def dfs(u):\n            for v in range(n):\n                if M[u][v] ==1 and visit[v] == False:\n                    visit[v] = True\n                    dfs(v)\n        \n        count = 0\n        for i in range(n):\n            if visit[i] == False:\n                count += 1\n                visit[i] = True\n                dfs(i)\n        \n        return count\n```
['Depth-First Search', 'Python', 'Python3']