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

connected-components-dfs.cpp

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

void DFSRec(vector<int> *G, int src, vector<bool> &visited) {
  visited[src] = true;
  for(int u: G[src])
    if(!visited[u])
      DFSRec(G, u, visited);
}

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

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

int main() {
  int t;  cin >> t;
  while(t--) {
    int V, E, u, v;   cin >> V >> E;
    vector<int> G[V];
    for(int i = 0; i < E; ++i) {
      cin >> u >> v;
      addEdge(G, u-1, v-1);
    }
    cout << DFSDisconnected(G, V) << endl;
  }
  return 0;
}