MiddleCodeOccasionalNot answered yet
Detect cycles and unreachable states in a directed graph
Analyze a directed graph given as an adjacency list. Implement hasCycle and unreachable (vertices not reachable from the given source set).
Requirements:
a back edge to a grey node is a cycle. A plain visited-flag is not enough.
- Cycle detection in O(V+E): use three-colour DFS (white / grey / black);
- Run DFS from every unvisited vertex so disconnected components are covered.
unreachable: DFS/BFS from all sources, then collect the unvisited vertices.
class Graph {
public:
explicit Graph(int n) : adj_(n), n_(n) {}
void addEdge(int u, int v) { adj_[u].push_back(v); }
bool hasCycle() const {
// your code here
}
std::vector<int> unreachable(const std::vector<int>& sources) const {
// your code here
}
private:
std::vector<std::vector<int>> adj_;
int n_;
};Write the implementation.
Use DFS with three-colour marking: white (unvisited), grey (in current path), black (fully processed). A back edge (grey→grey) indicates a cycle. Unreachable nodes remain white after a full DFS from all source nodes. A deadlock state is a cycle in a dependency/wait-for graph.
- ✗Using only a visited set — it detects visited nodes but not back edges (on-path vs already-completed)
- ✗Not performing DFS from all unvisited nodes — misses disconnected components
- ✗Confusing undirected-graph cycle detection (union-find) with directed-graph cycle detection (DFS colours)
- →How does topological sort relate to cycle detection in a DAG?
- →What is Tarjan's algorithm for finding strongly connected components?
Contents
Task
Analyze a directed graph: detect cycles and find unreachable vertices from given sources.
Key points
- Three-colour DFS: white (unvisited), grey (in path), black (done). Back edge = cycle.
- Unreachable nodes: run DFS/BFS from all sources, collect unvisited nodes.
- O(V+E) for both operations.
Contents
