# DFS Recursive C++

• ``````class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> neighbors (n, vector<int> ());
vector<bool> nodesVisited (n, false);
int edgesSize = edges.size() + 1;

int first, second;
for(int i = 0; i < edges.size(); i++){
first = edges[i].first;
second = edges[i].second;
neighbors[second].push_back(first);
neighbors[first].push_back(second);
}

dfs(edges, nodesVisited, edgesSize, neighbors, 0);
for(int i = 0; i < n; i++)
if(!nodesVisited[i]) return false;
if(edgesSize > 0) return false;
return true;
}
void dfs(vector<pair<int, int>>& edges, vector<bool> &nodesVisited, int &edgesSize, vector<vector<int>> &neighbors, int node){
if(nodesVisited[node]) return;
else{
nodesVisited[node] = true;
edgesSize--;
}
for(int i = 0; i < neighbors[node].size(); i++){
if(neighbors[node][i] != node)
dfs(edges, nodesVisited, edgesSize, neighbors, neighbors[node][i]);
}
return;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.