Java Detailed Solution for beginners 🚀🚀🚀🚀
Approach\n1. Construct a Graph Representation:\nFirst, we convert the adjacency matrix into a graph representation that\'s easier to traverse. Each node (or cit
# Approach\n1. **Construct a Graph Representation:**\nFirst, we convert the adjacency matrix into a graph representation that\'s easier to traverse. Each node (or city) is connected \u27A1\uFE0F to its neighbors a based on the matrix. For each `1` in the adjacency matrix that isn\'t on the diagonal (ignoring self-loops), we add a connection.\n\n\n    ```\n    public Map<Integer, List<Integer>> makeGraph(int[][] connected) {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        for (int i = 0; i < connected.length; i++) {\n            graph.put(i, new ArrayList<>());  // Initialize a list for each node\n        }\n        for (int i = 0; i < connected.length; i++) {\n            for (int j = 0; j < connected[i].length; j++) {\n                if (connected[i][j] == 1 && i != j) {  // Ensure we are adding only valid connections\n                    graph.get(i).add(j);  // Add a connection from node i to node j\n                }\n            }\n        }\n        return graph;  // Return the fully formed graph\n    }\n    ```\n2. **Depth First Search (DFS) to Explore Connected Components:**\nWe use a recursive DFS to explore each node\'s connections thoroughly. Once we start a DFS from a node, we mark all reachable nodes as visited, which means they all belong to the same province.\n\n    ```\n    public void dfs(int node, Map<Integer, List<Integer>> graph, boolean[] visited) {\n        visited[node] = true;  // Mark this node as visited\n        List<Integer> neighbors = graph.get(node);  // Get all direct connections\n\n        for (int neighbor : neighbors) {\n            if (!visited[neighbor]) {  // If the neighbor hasn\'t been visited\n                this.dfs(neighbor, graph, visited);  // Recursively visit this node\n            }\n        }\n    }\n    ```\n\n3. **Count Provinces by Initiating DFS Where Necessary:**\nWe iterate through all nodes and initiate a DFS from each unvisited node. Each initiation of DFS corresponds to a new province, and thus, we increase our province count each time we start a new DFS from an unvisited node.\n    ```\n    public int findCircleNum(int[][] isConnected) {\n        Map<Integer, List<Integer>> graph = makeGraph(isConnected);\n        boolean[] visited = new boolean[isConnected.length];\n        int provinces = 0;\n        for (int i = 0; i < isConnected.length; i++) {\n            if (!visited[i]) {  // If this node has not been visited\n                this.dfs(i, graph, visited);  // Perform DFS from this node\n                provinces++;  // Increment the province count\n            }\n        }\n        return provinces;  // Return the total number of provinces found\n    }\n    ```\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ - The time complexity of this solution is $$O(n^2)$$, where $$n$$ is the number of cities or nodes in the matrix `isConnected`. The complexity arises from two main operations:\n\n    - The `makeGraph` method iterates through every element in the `isConnected` matrix, which is a $$n\xD7n$$ matrix, to construct the adjacency list representation of the graph.\n\n    - The DFS traversal is invoked for each unvisited node to explore all its connected components. While each DFS call itself might seem \uD83E\uDD28 to explore multiple nodes more than once across different calls, each node is `visited` exactly once \uD83E\uDD17 due to the visited array check.\n\n- Space complexity:\n$$O(n)$$ - The space complexity is $$O(n)$$. The main contributors to space complexity are:\n\n    - The adjacency list, which in the worst case (when every node is connected to every other node) contains $$n$$ lists, each potentially with up to $$n$$ entries. However, in practice, because *each edge (connection) is only stored once, it contributes linearly to the space.*\n\n    - A `visited` array of size $$n$$ that keeps track of which nodes have been visited.\n\n# Code\n```\nclass Solution {\n    public int findCircleNum(int[][] isConnected) {\n        Map<Integer, List<Integer>> graph = makeGraph(isConnected);\n        boolean[] visited = new boolean[isConnected.length];\n        int provinces = 0;\n        for (int i = 0; i < isConnected.length; i++) {\n            if (visited[i]) continue;\n            this.dfs(i, graph, visited);\n            provinces++;\n        }\n        return provinces;\n\n    }\n\n    public void dfs(int node, Map<Integer, List<Integer>> graph, boolean[] visited) {\n        visited[node] = true;\n        List<Integer> nbrs = graph.get(node);\n\n        for (int nbr : nbrs) {\n            if (!visited[nbr])\n                this.dfs(nbr, graph, visited);\n        }\n    }\n\n    public Map<Integer, List<Integer>> makeGraph(int[][] connected) {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        for (int i = 0; i < connected.length; i++) {\n            graph.put(i, new ArrayList<>());\n        }\n        for (int i = 0; i < connected.length; i++) {\n            for (int j = 0; j < connected[0].length; j++) {\n                if (connected[i][j] == 1)\n                    graph.get(i).add(j);\n            }\n        }\n        return graph;\n    }\n}\n```
['Depth-First Search', 'Java']