You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [aᵢ, bᵢ] indicates that there is an edge between aᵢ and bᵢ in the graph.
Return the number of connected components in the graph.
Example 1:
Input:
n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2Example 2:
Input:
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1Constraints:
1 <= n <= 20001 <= edges.length <= 5000edges[i].length == 20 <= aᵢ <= bᵢ < naᵢ != bᵢ- There are no repeated edges.
Topics
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number vertices and E is the number of edges in the graph.
Hint 1
Assume there are no edges initially, so we have n components, as there are that many nodes given. Now, we should add the given edges between the nodes. Can you think of an algorithm to add the edges between the nodes? Also, after adding an edge, how do you determine the number of components left?
Hint 2
We can use the Union-Find (DSU) algorithm to add the given edges. For simplicity, we use Union-Find by size, where we merge the smaller component into the larger one. The Union-Find algorithm inserts the edge only between two nodes from different components. It does not add the edge if the nodes are from the same component. How do you find the number of components after adding the edges? For example, consider that nodes 0 and 1 are not connected, so there are initially two components. After adding an edge between these nodes, they become part of the same component, leaving us with one component.
Hint 3
We create an object of the DSU and initialize the result variable res = n, which indicates that there are n components initially. We then iterate through the given edges. For each edge, we attempt to connect the nodes using the union function of the DSU. If the union is successful, we decrement res; otherwise, we continue. Finally, we return res as the number of components.