Hard
DFS cycle detection on a diamond-shaped graph
Run this cycle-check on the DAG A→B, A→C, B→D, C→D (a diamond: D is reachable from A via two distinct paths, but there is no actual cycle), starting with dfs(A). Does hasCycle end up true or false, and is that correct?
main.cpp
unordered_set<int> visited;
bool hasCycle = false;
void dfs(int u, vector<vector<int>>& adj) {
visited.insert(u);
for (int v : adj[u]) {
if (visited.count(v)) {
hasCycle = true;
} else {
dfs(v, adj);
}
}
}21 of 46 in Data Structures & Algorithms