Path in a Graph

path-in-graph.cpp

// Check if there exists a Path from given vertices: (u, v)
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool DFSRec(vector<int> *G, int src, int dest, vector<bool> &visited) {
  if(src == dest) return true;
  visited[src] = true;
  for(int u: G[src])
    if(!visited[u])
      if(DFSRec(G, u, dest, visited)) // important step: cannot directly return the truth value, have to test whether true/false, then return
        return true;
  return false;
}

bool DFS(vector<int> *G, const int V, int src, int dest) {
  vector<bool> visited(V+1, false);
  return DFSRec(G, src, dest, visited);
}

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;
  for(int i = 0; i < t; ++i) {
    int V, E, u, v;   cin >> V >> E;
    vector<int> G[V+1];
    for(int i = 0; i < E; ++i) {
      cin >> u >> v;
      addEdge(G, u, v);
    }
    
    int Q;  cin >> Q; // #Queries
    cout << "Test Case #" << i+1 << ":\n";
    while(Q--) {
      cin >> u >> v;
      cout << (DFS(G, V, u, v) ? "Yes" : "No") << "\n";
    }
  }
  return 0;
}