Hi EPI,
I found the implementation of the Team Reachability DFS graphs bootcamp solution to be difficult to understand. Especially because most implementations of DFS use two functions (DFS and DFSRecursiveHelper).
To demonstrate, I implemented what I thought to be a simpler solution. I’ve tested against your implementation and both give the same result using your main() function. Please let me know if my code below isn’t optimal or fails on certain cases.
bool kIsReachableDFS(const unordered_map<string, unordered_set<string>>& graph, const string& curr, const string& dest){
if(curr == dest){
return true;
}
unordered_set<string> visited;
if(kIsReachableDFSHelper(graph, curr, dest, &visited)){
return true;
}
return false;
}
bool kIsReachableDFSHelper(const unordered_map<string, unordered_set<string>>& graph, const string& curr, const string& dest, unordered_set<string>* visited_ptr){
unordered_set<string>& visited = *visited_ptr;
visited.emplace(curr);
if(curr == dest){
return true;
}
if(graph.find(curr) == graph.end()){
return false;
}
const unordered_set<string>& teamsBeat = graph.at(curr);
unordered_set<string>::const_iterator it;
for(it = teamsBeat.begin(); it != teamsBeat.end(); ++it){
if(visited.find(*it) == visited.end()){
if(kIsReachableDFSHelper(graph, *it, dest, visited_ptr)){
return true;
}
}
}
return false;
}