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 between x and y in the graph.

Constraints:

• $1 \leq$ n $\leq 2000$

• $1 \leq$ edges.length $\leq 5000$

• edges[i].length $== 2$

• $0 \leq$ x $\leq$ y $\lt$ n

• x $\neq$ y

• There are no repeated edges.

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 element v, it recursively finds and returns the representative (root) of the set that v 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 future find operations by making each element point directly to its root.

• union(): For any two given elements x and y, it checks their root representatives using the find() method.

  • If the roots are the same, it means x and y are already in the same set, so no action is taken, and the method returns FALSE.

  • Otherwise, it merges the sets containing x and y 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 subsequent find and union 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) in edges, it calls the union() method of the dsu instance (from the Union Find class) with x and y as arguments.

• If the union operation returns TRUE, it means that the x and y nodes were not in the same component before the union, and they have now been united. In this case, the value of res is decremented by 1.

  • 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: