Number of Connected Components

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Number of Connected Components** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Union-Find or DFS count of starts **Edge Cases to Consider:** - (1) No edges - (2) All connected - (3) Self-loops

Examples

Example 1

Input: 5, [[0,1],[1,2],[3,4]]

Output: 2

Explanation: Two components

Example 2

Input: 5, [[0,1],[1,2],[2,3],[3,4]]

Output: 1

Explanation: Fully connected chain

Example 3

Input: 1, []

Output: 1

Explanation: Single node

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪No edges
▪All connected
▪Self-loops

Frequently Asked At

AmazonMicrosoftAdobeFlipkart

Back to Arena

medium

Graph

Number of Connected Components

Examples

Example 1

Input: 5, [[0,1],[1,2],[3,4]]

Output: 2

Explanation: Two components

Example 2

Input: 5, [[0,1],[1,2],[2,3],[3,4]]

Output: 1

Explanation: Fully connected chain

Example 3

Input: 1, []

Output: 1

Explanation: Single node

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪No edges
▪All connected
▪Self-loops

Frequently Asked At

AmazonMicrosoftAdobeFlipkart