Finding connected components in a graph

Problem Statement

Given a graph with V vertices and E edges, find the number of connected components.

Note: This is not the same as finding the number of strongly connected components

General Idea | \(O(V+E)\)

The general idea is to simply start traversing from any vertex (for simplicity, we start from vertex 0). DFS or BFS should both work fine here. A search from any vertex v will find the entire connected component containing v before returning.

To find all the connected components of a graph, we loop through all its vertices, starting a new DFS or BFS search whenever the loop reaches a vertex that has not been already included in a previously found connected component.

Wikipedia

Code

C++ code below, using DFS

vector<bool> visited;
int number_of_connected_components = 0;

int main()
{
    //V -> each vertex from [0..V-1]
    for(int i = 0; i < V; i++)
        if(!visited[i])
        {
            number_of_connected_components++;
            dfs(i);
        }
}