Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Intermediate Level

Implement the connectedComponentsCount method that counts connected components in an undirected graph.

The input represents an undirected graph. nodes is the total number of vertices, numbered from 0 to nodes - 1, and edges contains pairs of connected vertices.

Your task is to count how many connected components are present in the graph. A connected component is a group of nodes where every node can be reached from another node in the same group.

For example, with 5 nodes and edges [[0,1],[1,2],[3,4]], nodes 0,1,2 form one component and nodes 3,4 form another, so the answer is 2.

Example 1
Input:
nodes (int) = 5
edges (int[][]) = [[0,1],[1,2],[3,4]]
size (int) = 3
Return:
(int) 2
Example 2
Input:
nodes (int) = 5
edges (int[][]) = []
size (int) = 0
Return:
(int) 5
Example 3
Input:
nodes (int) = 3
edges (int[][]) = [[0,1],[1,2]]
size (int) = 2
Return:
(int) 1

Build an adjacency list from the edge list, then visit every node using DFS or BFS.

Whenever you find a node that has not been visited yet, it means a new connected component has started. Increase the component count and traverse from that node to mark all nodes in the same component as visited.

After all nodes are checked, the count gives the total number of connected components.

Pseudocode:

function connectedComponentsCount(nodes, edges, size):
    graph = create adjacency list for nodes
    for each edge [u, v] in edges:
        add v to graph[u]
        add u to graph[v]
    visited = array filled with false
    components = 0
    for node from 0 to nodes - 1:
        if visited[node] == false:
            components++
            dfs(node)
    return components
function dfs(node):
    visited[node] = true
    for each nextNode in graph[node]:
        if visited[nextNode] == false:
            dfs(nextNode)
Run your code to see the result.