547.md

547. Number of Provinces

Solution 1 (time O(n^2), space O(n))

# DFS
class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        n = len(isConnected)
        vis = [False] * n

        def dfs(i):
            vis[i] = True
            for j in range(n):
                if isConnected[i][j] == 1 and not vis[j]:
                    dfs(j)

        ans = 0
        for i in range(n):
            if not vis[i]:
                dfs(i)
                ans += 1
        return ans