undirected graph is represented by:

A number of nodes, n (labelled 0 to n-1).
A list of edges, each representing a connection between any two nodes.

To find the number of connected components:

Think of this problem as identifying clusters of connected nodes in the graph.
Use Graph Traversal Algorithms:
- DFS (Depth First Search) or BFS (Breadth First Search) to explore each connected component fully.
Maintain an array to track visited nodes. Each time you encounter an unvisited node, it's the start of a new connected component.

Algorithm

Create an adjacency list to store the graph from the input edges.
Use a visited array to track whether a node has been visited.
Perform a DFS or BFS from each unvisited node, marking all connected nodes as visited during traversal. For each traversal, increment the connected components count.
Return the count of connected components.

Code

[{"language":"Java","code":"class Solution {\n    public int countComponents(int n, int[][] edges) {\n        // Create adjacency list\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        for (int i = 0; i < n; i++) {\n            graph.put(i, new ArrayList<>());\n        }\n        for (int[] edge : edges) {\n            graph.get(edge[0]).add(edge[1]);\n            graph.get(edge[1]).add(edge[0]);\n        }\n        \n        // Visited set to track visited nodes\n        boolean[] visited = new boolean[n];\n        \n        // DFS Helper function\n        void dfs(int node) {\n            visited[node] = true;\n            for (int nei : graph.get(node)) {\n                if (!visited[nei]) {\n                    dfs(nei);\n                }\n            }\n        }\n        \n        int ans = 0;\n        // Iterate through all nodes\n        for (int i = 0; i < n; i++) {\n            if (!visited[i]) {\n                ans++; // A new component\n                dfs(i); // Explore the entire component\n            }\n        }\n        \n        return ans;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n        # Create adjacency list\n        graph = {i: [] for i in range(n)}\n        for u, v in edges:\n            graph[u].append(v)\n            graph[v].append(u)\n        \n        # Visited set to keep track of visited nodes\n        visited = [False] * n\n        \n        def dfs(node: int) -> None:\n            # Mark current node as visited\n            visited[node] = True\n            for nei in graph[node]:\n                if not visited[nei]:\n                    dfs(nei)\n        \n        ans = 0\n        # Iterate through all nodes\n        for i in range(n):\n            if not visited[i]:\n                ans += 1  # A new component\n                dfs(i)    # Explore the entire component\n        \n        return ans","lang":"python"}]

Complexity

⏰ Time complexity: O(V + E) due to DFS
🧺 Space complexity: O(V + E), Storing adjacency list uses O(V + E) space, and visited array uses O(V) space.

Method 2 - Union Find

This problem can be solved by using union-find beautifully. Initially, there are n nodes. The nodes that are involved in each edge is merged.

We can use Disjoint Set - Union by Rank Implementation

Here is the approach:

Treat each node as its own component initially.
Use the Union-Find/Disjoint Set data structure to group connected nodes together:
- Union

Related Tags

Continue Practicing