DFS Brute Force Java Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem at hand is to find the number of connected components in a graph represente
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem at hand is to find the number of connected components in a graph represented by an adjacency matrix isConnected. Each node represents a city, and an edge between two nodes (cities) means they are directly connected.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe initialize an array visited to keep track of visited cities.\nWe iterate through each city (node) using a loop. If a city hasn\'t been visited yet (visited[i] is false), it indicates the start of a new connected component.\nWe then perform DFS from this city to mark all cities reachable from it.\nEach time we initiate a DFS from an unvisited city, we increment our count of connected components.\n\n# Complexity\n- Time complexity: o(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int findCircleNum(int[][] isConnected) {\n        int n = isConnected.length;\n        boolean[] visited = new boolean[n];\n        int count = 0;\n\n        for (int i = 0; i < n; i++) {\n            if (!visited[i]) {\n                dfs(isConnected, visited, i);\n                count++;\n            }\n        }\n        return count;\n    }\n    private void dfs(int[][] isConnected, boolean[] visited, int i) {\n        visited[i] = true;\n        for (int j = 0; j < isConnected.length; j++) {\n            if (isConnected[i][j] == 1 && !visited[j]) {\n                dfs(isConnected, visited, j);\n            }\n        }\n    }\n}\n\n```
['Java']