Find Eventual Safe States

74.8k
0

Given a directed graph represented by an adjacency list, return all eventual safe nodes in ascending order.

A terminal node has no outgoing edges. A safe node is a node from which every possible directed path eventually reaches a terminal node instead of getting trapped in a cycle.

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

Explanation: Nodes 2, 4, 5, and 6 cannot reach a directed cycle.

Example 2

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Output: [4]

Explanation: Only node 4 is guaranteed to end at a terminal node.

Approach 1

Depth First Search tracks globally visited nodes, nodes in the active recursion path, and nodes proven safe. Reaching an active node confirms a directed cycle, while reaching a previously identified unsafe node confirms a path leading to a cycle.

A node becomes safe only after every outgoing path reaches a safe node or a terminal node. Scanning the final safe array from index 0 to V-1 produces ascending output.

Algorithm

  • Initialize visited, pathVisited, and safe arrays of size V to track explored nodes, active-path nodes, and proven safe nodes.

  • Traverse every node and start DFS from each unvisited node, ensuring coverage of all disconnected directed components.

  • Mark the current node as visited and active in pathVisited before exploring outgoing edges.

  • Return an unsafe result upon reaching an active neighbor, as an edge to the current recursion path confirms a directed cycle.

  • Continue DFS for every unvisited neighbor; an unsafe recursive result or a previously visited unsafe neighbor also makes the current node unsafe.

  • Remove the current node from pathVisited and mark the node safe only after every outgoing neighbor is proven safe.

  • Scan nodes from 0 to V-1, collect all nodes marked safe, and return the resulting ascending list.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks whether a node is safe using DFS.
bool dfs(int node, vector<int>& visited, vector<int>& pathVisited,
vector<int>& safe, vector<vector<int>>& graph) {
// Mark node as visited.
visited[node] = 1;
// Mark node in active DFS path.
pathVisited[node] = 1;
// Explore all outgoing neighbors.
for (int neighbor : graph[node]) {
// Visit unvisited neighbor first.
if (!visited[neighbor]) {
// Unsafe neighbor makes current node unsafe.
if (!dfs(neighbor, visited, pathVisited, safe, graph)) {
return false;
}
}
// Active-path neighbor confirms a cycle.
else if (pathVisited[neighbor]) {
return false;
}
// Previously visited unsafe neighbor makes current node unsafe.
else if (!safe[neighbor]) {
return false;
}
}
// Remove node from active DFS path.
pathVisited[node] = 0;
// Mark node as safe after all paths pass.
safe[node] = 1;
// Return safe status for current node.
return true;
}
public:
// Returns all eventual safe nodes in ascending order.
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int vertices = graph.size();
vector<int> visited(vertices, 0);
vector<int> pathVisited(vertices, 0);
vector<int> safe(vertices, 0);
// Start DFS from every unvisited node.
for (int node = 0; node < vertices; node++) {
if (!visited[node]) {
dfs(node, visited, pathVisited, safe, graph);
}
}
vector<int> answer;
// Collect safe nodes in ascending order.
for (int node = 0; node < vertices; node++) {
if (safe[node]) {
answer.push_back(node);
}
}
// Return all safe nodes.
return answer;
}
};
// Driver code.
int main() {
vector<vector<int>> graph = {
{1, 2},
{2, 3},
{5},
{0},
{5},
{},
{}
};
Solution sol;
vector<int> answer = sol.eventualSafeNodes(graph);
for (int node : answer) {
cout << node << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of nodes and directed edges; DFS processes every node and edge once.

Space Complexity: O(V), where the state arrays and recursive DFS stack store a number of entries proportional to V.

Approach 2

Reverse Kahn’s Algorithm begins from terminal nodes, which are safe because no outgoing paths exist. Reversing every directed edge allows safe-state propagation from terminal nodes toward predecessors.

The outdegree of a predecessor decreases whenever one outgoing neighbor is proven safe. An outdegree of 0 confirms that every outgoing path leads to a safe node.

Algorithm

  • Build a reverse adjacency list and compute the original outdegree of every node, allowing safe states to propagate toward predecessors.

  • Add all nodes having outdegree 0 to a queue, since terminal nodes are safe by definition.

  • Initialize a safe array to record every node proven to have no path leading to a directed cycle.

  • Continue processing while the queue contains nodes, removing the front node and marking the node safe.

  • Traverse every predecessor in the reverse graph and decrease the predecessor’s outdegree, representing one outgoing path proven safe.

  • Add a predecessor to the queue when the outdegree becomes 0, as all outgoing paths now lead to safe nodes.

  • Scan nodes from 0 to V-1, collect all marked nodes, and return the resulting ascending list.

Dry Run

eventual-safe-nodes-reverse-kahn-complete-operations

eventual-safe-nodes-reverse-kahn-complete-operations

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find safe nodes using reverse Kahn BFS.
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int vertices = graph.size();
vector<vector<int>> reverseGraph(vertices);
vector<int> outdegree(vertices, 0);
// Reverse edges and count original outgoing edges.
for (int node = 0; node < vertices; node++) {
outdegree[node] = graph[node].size();
for (int neighbor : graph[node]) {
reverseGraph[neighbor].push_back(node);
}
}
queue<int> q;
// Terminal nodes are safe starting points.
for (int node = 0; node < vertices; node++) {
if (outdegree[node] == 0) {
q.push(node);
}
}
vector<int> safe;
// Remove safe terminal paths from predecessors.
while (!q.empty()) {
int node = q.front();
q.pop();
safe.push_back(node);
for (int predecessor : reverseGraph[node]) {
outdegree[predecessor]--;
if (outdegree[predecessor] == 0) {
q.push(predecessor);
}
}
}
sort(safe.begin(), safe.end());
return safe;
}
};
// Driver code.
int main() {
vector<vector<int>> graph = {{1,2},{2,3},{5},{0},{5},{},{}};
Solution sol;
vector<int> ans = sol.eventualSafeNodes(graph);
// Print safe nodes.
for (int node : ans) {
cout << node << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of nodes and directed edges; every node and reversed edge is processed once.

Space Complexity: O(V+E), where the reverse graph stores V nodes and E edges, while the outdegree array, safe array, and queue require O(V) space.

Interview follow-up Questions

An eventual safe node has every possible path ending at a terminal node.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0