# Graph Valid Tree C++ solution using DFS

• ``````class Solution {
int cc;
public:
bool dfs(int src, int target, vector<unordered_set<int>> &adj, vector<bool> &marked) {
// dfs  to check for connectedness from src to target
for (auto &dest : adj[src]) {
if (dest == target) return true;
if (!marked[dest]) {
marked[dest] = true;
if(dfs(dest, target, adj, marked)) return true;
}
}
return false;
}
void dfs(int src, vector<unordered_set<int>> &adj, vector<bool> &marked) {
// plain dfs from src
for (auto &dest : adj[src]) {
if (!marked[dest]) {
marked[dest] = true;
}
}

}
bool graph_connected(vector<unordered_set<int>> &adj, int n) {
// count number of components
cc = 0;
vector<bool> marked(n, false);
for (size_t src = 0; src < n; ++src) {
if(!marked[src]) {
marked[src] = true;
cc++;
if (cc > 1) return false; // more than one connected component
}
}
return true;
}
bool validTree(int n, vector<pair<int, int>>& edges) {
if(n <= 1) return true;
for (auto &e : edges) {
vector<bool> marked(n, false);
marked[e.first] = true;
if (dfs(e.first, e.second, adj, marked)) return false; // cycle exists