Java | DFS | Beats > 98% | 13 lines | Clean code
Complexity\n- Time complexity: O(n^2)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n) on the stack\n Add your space complexity here, e.g
# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ on the stack\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  private void dfs(int city, int[][] isConnected, boolean[] seen) {\n    seen[city] = true;\n\n    for (var i = 0; i < isConnected.length; i++)\n      if (isConnected[city][i] == 1 && !seen[i])\n        dfs(i, isConnected, seen);\n  }\n\n  public int findCircleNum(int[][] isConnected) {\n    var n = isConnected.length;\n    var seen = new boolean[n];\n    var cnt = 0;\n\n    for (var i=0; i<n; i++) {\n      if (!seen[i]) {\n        dfs(i, isConnected, seen);\n        cnt++;\n      }\n    }\n    return cnt;\n  }\n}\n```\nIf you like my solution, please upvote it!
['Depth-First Search', 'Graph', 'Java']