Count Number of Connected Components

Code

// C++ program for counting connected components
#include <bits/stdc++.h>
using namespace std;

// Graph class for an undirected graph
class Graph {
// no. of vertices
int n;

// pointer to an array containing adjacency list representation of the graph

vector<int>* adj;

// function for depth-first-search
void DFS(int v, bool visited[]);

public:
// Constructor
Graph(int n);

void addEdge(int u, int v);
int NumberOfconnectedComponents();
};

// Function to return the number of
// connected components in an undirected graph
int Graph::NumberOfconnectedComponents()
{


bool* visited = new bool[n];


// marking all the vertices as  unvisited
int count = 0;
for (int v = 0; v < n; v++)
visited[v] = false;

  //iterating over all the vertices
for (int v = 0; v < n; v++) {
if (visited[v] == false) {
DFS(v, visited);
count += 1;
}
}

return count;
}

void Graph::DFS(int v, bool visited[])
{

// Mark the current node as visited
visited[v] = true;


// recursively calls  itself for its adjacent nodes 

    for( auto child:adj[v])
    {
     if(!visited[child])
     {
     DFS(child,visited);
}
}

}

Graph::Graph(int n)
{
this->n= n;
adj = new vector<int>[n];
}

// adding an undirected edge
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}

// Driver code
int main()
{
Graph g(6);
g.addEdge(1, 3);
g.addEdge(0, 4);
g.addEdge(5, 4);

    cout<<"no. of connected components: ";
cout << g.NumberOfconnectedComponents();

return 0;
}

Output

no. of connected components: 3

Complexity Analysis

• Time Complexity: We have implemented this algorithm using DFS. So,  its complexity is the same as DFS, O (n+e), where n is the number of vertices and e is the number of edges in the graph.
• Space Complexity: Here, in the worst-case recursion stack size for DFS can become n.So, space complexity is O(n).

You can also read Detect cycle in an undirected graph here.

Recommended Topic - Strong number in c

FAQs

1. What is an undirected graph?
   If edges between two nodes don’t have any specific direction in a graph, the graph is undirected.
    
2. What is cut edge?
   If removal of an edge creates more connected components in a graph, the edge is called a cut edge or bridge.
    
3. What is a cut vertex?
   If the removal of a vertex creates more connected components in a graph, the edge is called a cut vertex.
    
4. What is SCC(strongly connected components)?
   The subgraphs of a directed graph that are strongly connected but not contained in larger strongly connected subgraphs are called strongly connected components.
   Here, strongly connected means there is a directed path between every pair of vertices.
    
5. How to count SCC?
   Here are two well-known algorithms, i.e., Kosaraju's algorithm and Tarjan's algorithm for counting strongly connected components.

Key Takeaways

This article discussed the concept of the connected components, counting the number of connected components in an undirected graph. The blog also tried to provide a better understanding of the time complexity for such an operation on a graph.
Check out this problem - No of Spanning Trees in a Graph

To learn more, head over right now to Coding Ninjas Studio to practice important graph-related problems and crack your interviews like a Ninja!

Happy learning!