Beginner Friendly - Using BFS and Adjacency list
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the number of connected components in an undirected graph.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the number of connected components in an undirected graph. Connected components are subsets of nodes in a graph where each node is reachable from any other node in the same subset.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1.Adjacency List Creation:**\n\nThe code begins by converting the given adjacency matrix isConnected into an adjacency list l. This conversion makes it easier to traverse the graph using lists of connected nodes for each node.\n**2.Breadth-First Search (BFS):**\n\nThe main part of the code utilizes BFS to explore the graph and count the number of connected components.\nIt starts by iterating through each node.\nFor each unvisited node encountered, it initiates a BFS to explore all nodes connected to that node.\nIt keeps track of visited nodes using a HashSet (visited) to ensure nodes are not visited more than once.\nDuring BFS, it traverses the connected nodes of the current node and marks them as visited, ensuring all nodes in the same component are accounted for.\n**3.Counting Connected Components:**\n\nEach time BFS is initiated from an unvisited node, it identifies a new connected component and increments the count variable to keep track of the total count of connected components.\n**4.Returning the Count:**\n\nFinally, the code returns the total count of connected components found in the graph.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int findCircleNum(int[][] isConnected) {\n\n        int n = isConnected.length; \n        // To create an adjacency list \'l\' \n        List<List<Integer>> l = new ArrayList<>();\n\n        // Creating adjacency list from the adjacency matrix\n        for (int i = 0; i < n; i++) {\n            l.add(new ArrayList<>());\n            for (int j = 0; j < n; j++) {\n                if (i != j && isConnected[i][j] == 1) {\n                    // Adding connected nodes to the adjacency list\n                    l.get(i).add(j);\n                }\n            }\n        }\n\n        Queue<Integer> q = new LinkedList<>();\n        HashSet<Integer> visited = new HashSet<>();\n        int count = 0; // Counter for connected components\n\n        // Checking for each node whether it has any path or is part of a disjoint component\n        for (int i = 0; i < n; i++) {\n            if (!visited.contains(i)) {\n                // Starting BFS from unvisited node\n                q.add(i);\n                visited.add(i);\n                while (!q.isEmpty()) {\n                    int current = q.poll();\n                    for (int j : l.get(current)) {\n                        if (!visited.contains(j)) {\n                            q.add(j);\n                            visited.add(j);\n                        }\n                    }\n                }\n                count++; // Increment count for each connected component found\n            }\n        }\n        return count; // Returning the total count of connected components\n    }\n}\n\n```\n![6f52fd51-764d-4d16-8687-d4d917526ef2_1698628883.3464968.jpeg](https://assets.leetcode.com/users/images/25e211e3-aab7-41ec-9253-f63066fe2949_1705484869.1293066.jpeg)\n\n\n\n
['Breadth-First Search', 'Java']