A connected component is a group of nodes where every node is reachable from every other node.

You are given:

n nodes
edges[][] 

Goal:

Find total number of connected components. 

Union Find (DSU) is one of the most efficient ways to solve this problem.

Example

Input:

n = 5edges = [[0,1],[1,2],[3,4]]

Output:

2 

Explanation:

Component 10 - 1 - 2

Component 2
3 - 4

Key Observation

Initially:

Every node is its own component.

Whenever two different components are connected:

Union(u,v) 

The total number of components decreases by one.

Algorithm

1. Initialize DSU2. Components = n
3. Process every edge
4. Union nodes
5. Reduce count
6. Return components

Input:

n = 5[0,1]
[1,2]
[3,4]

Initially:

5 Components

After Union(0,1):

4 Components 

After Union(1,2):

3 Components 

After Union(3,4):

2 Components 

Final Answer:

2

Approach : Union Find (DSU)

Explanation

Every node starts as its own parent.

For every edge:

1. Find the parent of both nodes.
2. If parents are different, merge them.
3. Reduce component count.
4. Continue for all edges.

The remaining count represents the number of connected components.

Practice

Time Complexity: O(E × α(N))We process every edge once and perform Union-Find operations.With path compression, each operation becomes nearly constant time.

Space Complexity: O(N)
We store a parent array of size N to keep track
of the connected components.

 InitiallyComponents = N
Every successful union
reduces components by 1.