Statementâ–¼
For a given integer, n
, and an array, edges
, return the number of connected components in a graph containing n
nodes.
Note: The array
edges[i] = [x, y]
indicates that there’s an edge betweenx
andy
in the graph.
Constraints:
1≤ n
≤2000 1≤ edges.length
≤5000 edges[i].length
==2 0≤ x
≤ y
< n
x
î€ = y
There are no repeated edges.
Solution
Since we are given an array of edges, and we are supposed to make connections and count the total number of components in the graph. For this purpose, we can take a union of the edges to make a component and then incrementally connect and count the overall number of connected components in the undirected graph. To do so, we will use the Union Find data structure, also known as Disjoint Set Union (DSU), that will find all of the graphs' connected components.
The union find data structure will have two primary methods:
find()
: For any given elementv
, it recursively finds and returns the representative (root) of the set thatv
belongs to. To find this representative, we'll use path compression during our traversal. Here's how we will implement path compression:On eachÂ
find
 operation on a tree node, we update the parent of that node to point directly to the root. This reduces the length of the path of that node to the root, ensuring we don’t have to travel all the intermediate nodes on futureÂfind
 operations. Doing so, we are optimizing futurefind
operations by making each element point directly to its root.
union()
: For any two given elementsx
andy
, it checks their root representatives using thefind()
method.If the roots are the same, it means
x
andy
are already in the same set, so no action is taken, and the method returns FALSE.Otherwise, it merges the sets containing
x
andy
based on the ranks of their respective roots. The root with the higher rank becomes the parent of the other root. This distinction of choosing the greater rank is a strategy known as "union find by rank".Union by rank:Â By using the "union by rank" strategy, the
union
method ensures that the resulting tree, after the union operation, remains balanced, preventing the creation of tall, skewed trees. This optimization helps keep the overall performance of the Union Find data structure efficient by reducing the time complexity of subsequentfind
andunion
operations.
If the ranks are equal, one root is chosen arbitrarily as the parent and its rank is incremented.
After a union of two vertices, the method returns TRUE to indicate a successful union.
After implementing the union find data structure, we'll create an instance of the Union Find class with n
elements. Here, we'll set up the initial disjoint sets. Using a result variable, res
, with the value of n
, we can keep track of the remaining components.
For each edge
(x, y)
inedges
, it calls theunion()
method of thedsu
instance (from the Union Find class) withx
andy
as arguments.If the
union
operation returns TRUE, it means that thex
andy
nodes were not in the same component before the union, and they have now been united. In this case, the value ofres
is decremented by1
.The purpose of decrementing
res
is to keep track of the remaining number of connected components.
After processing all the edges, the function returns the final value of
res
, which represents the count of connected components in the graph.
The slides below illustrate how the algorithm runs: