Count Number of Connected Components [TC: O(V+E); SC: O(V+E)]

connected-components-bfs.cpp

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void addEdge(vector<int> *adj, int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}

void BFS(vector<int> *G, int V, int s, vector<bool> &vis) {
  queue<int> Q;
  vis[s] = true;
  Q.push(s);
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    // cout << u << " "; // To print the vertices in graph G
    for(int v: G[u])
      if(!vis[v]) {
        vis[v] = true;
        Q.push(v);
      }
  }
}

int BFSDisconnected(vector<int> *G, int V) {
  int count = 0;
  vector<bool> visited(V+1, false);
  for(int i = 0; i < V; ++i)
    if(!visited[i])
       ++count, BFS(G, V, i, visited);
  return count;
}

int main() {
  int t;  cin >> t;
  while(t--) {
    int vertices, edges, u, v; 
    cin >> vertices >> edges;
    
    // Initialize the graph: G(V, E) -> represented as G[u][v]
    vector<int> G[vertices];
    for(int i = 0; i < edges; ++i) {
      cin >> u >> v;
      addEdge(G, u-1, v-1); // for 0-based indexing
    }
    
    cout << BFSDisconnected(G, vertices) << "\n";
  }
  return 0;
}