DFS Solution || JAVA
Approach\nThe given code appears to be an implementation of finding the number of connected components in an undirected graph represented by an adjacency matrix
# Approach\nThe given code appears to be an implementation of finding the number of connected components in an undirected graph represented by an adjacency matrix. The approach used is Depth-First Search (DFS). Here\'s a step-by-step breakdown of the approach:\n\n1. Create an `ArrayList` of `ArrayList<Integer>` named `adj` to represent the adjacency list of the graph.\n\n2. Iterate over each row in the given 2D array `v` (which represents the adjacency matrix of the graph).\n\n3. For each pair of vertices (i, j) where `v[i][j]` is 1 and `i` is not equal to `j`, it means there is an edge between vertex `i` and vertex `j`.\n\n4. Add `j` to the adjacency list of `i` and add `i` to the adjacency list of `j`. This step establishes the undirected nature of the graph.\n\n5. Create a boolean array `visit` of length `v.length` to keep track of visited vertices. Initially, all elements are set to `false`.\n\n6. Initialize a variable `count` to keep track of the number of connected components.\n\n7. Iterate over each vertex in the graph (from 0 to `v.length - 1`).\n\n8. If the current vertex `i` has not been visited (`!visit[i]`), it means it belongs to a new connected component. Increment `count` and call the `dfs` function with the current vertex, adjacency list (`adj`), and the `visit` array.\n\n9. The `dfs` function performs the depth-first search traversal. It marks the current vertex `v` as visited (`visit[v] = true`) and then recursively calls `dfs` on all adjacent vertices that have not been visited.\n\n10. Finally, return the value of `count`, which represents the number of connected components in the graph.\n\nThe overall approach uses DFS to explore the graph and find all connected components by traversing through adjacent vertices. The `adj` list is used to represent the graph efficiently, and the `visit` array helps keep track of visited vertices to avoid redundant exploration.\n\nPlease note that the code assumes that the input graph is represented as an adjacency matrix (`v`) and it starts the DFS traversal from vertex 0.\n\n# Complexity\n- Time complexity:\n    - O(N^2)\n- Space complexity:\n    - O(N^2)\n\n# Code\n```\nclass Solution {\n    public int findCircleNum(int[][] v) {\n        ArrayList<ArrayList<Integer>> adj=new ArrayList();\n       for(int i=0;i<v.length;i++) adj.add(new ArrayList<>());\n       for(int i=0;i<v.length;i++){\n           for(int j=0;j<v.length;j++){\n               if(v[i][j]==1 && i!=j){\n                   adj.get(i).add(j);\n                   adj.get(j).add(i);\n               }\n           }\n       }\n        boolean[] visit=new boolean[v.length];\n        visit[0]=false;\n        int count=0;\n        for(int i=0;i<v.length;i++){\n            if(!visit[i]){\n                count++;\n                dfs(i,adj,visit);\n            }\n        }\n\n        return count;\n    }\n      static  void dfs(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visit){\n        visit[v]=true;\n        for(Integer i:adj.get(v)){\n            if(!visit[i]){\n                dfs(i,adj,visit);\n            }\n        }\n    }\n}\n```
['Java']