Check if Graph is Forest or Not [TC: O(V+E); SC: O(V)]

forest-graph-or-not.cpp

// Forest Definition: Disjoint Union of Acyclic Graphs (or Trees)
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool DFSRec(vector<int> *G, vector<bool> &visited, int curr, int parent) {
  visited[curr] = true;
  for(int adj: G[curr]) {
    if(!visited[adj]) {
      if(DFSRec(G, visited, adj, curr))
        return true;
    }
    else if(adj != parent)
      return true;
  }
  return false;
}

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

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 << (DFS(G, V) ? "No" : "Yes") << "\n";
  }
  return 0;
}