03. Safe States
✅ GFG solution to the Safe States problem: find all safe nodes in a directed graph where every path leads to a terminal node using reverse topological sort technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given a directed graph with V vertices numbered from 0 to V-1 and E directed edges, represented as a 2D array edges[][], where each element edges[i] = [u, v] represents a directed edge from vertex u to vertex v. Your task is to return all Safe Nodes of the graph.
A vertex with no outgoing edges is called a terminal node. A vertex is considered safe if every path starting from it eventually reaches a terminal node (i.e., it doesn't lead to a cycle or get stuck in an infinite loop).
📘 Examples
Example 1
Input: V = 5, E = 6, edges[][] = [[1, 0], [1, 2], [1, 3], [1, 4], [2, 3], [3, 4]]
Output: [0, 1, 2, 3, 4]
Explanation: Vertices 4 and 0 are terminal nodes (no outgoing edges).
All paths from vertices 1, 2, and 3 eventually lead to terminal node 4.
Therefore, all nodes are safe.Example 2
Input: V = 4, E = 3, edges[][] = [[1, 2], [2, 3], [3, 2]]
Output: [0]
Explanation: Vertex 0 is a terminal node with no outgoing edges.
Vertices 2 and 3 form a cycle, making vertex 1 unsafe.
Only vertex 0 is safe.🔒 Constraints
$1 \le V \le 10^5$
$0 \le E \le 10^5$
$0 \le \text{edges}[i][0], \text{edges}[i][1] < V$
✅ My Approach
The optimal approach uses Reverse Topological Sort with BFS (Kahn's Algorithm) to efficiently identify safe nodes:
Reverse Topological Sort + BFS
Build Reverse Graph:
Create a reversed adjacency list where edges point backward.
Calculate outdegree for each node (number of outgoing edges in original graph).
Initialize Queue:
Add all terminal nodes (outdegree = 0) to the queue.
Mark these nodes as safe.
Process Nodes:
Dequeue a safe node and process its predecessors in the reverse graph.
Decrement the outdegree of each predecessor.
If a predecessor's outdegree becomes 0, mark it safe and add to queue.
Collect Results:
After processing, collect all nodes marked as safe.
These are nodes from which all paths lead to terminal nodes.
Key Insight:
By reversing the graph and starting from terminal nodes, we propagate safety backward.
A node is safe only when all its outgoing paths have been verified as safe.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(V + E), as we traverse each vertex and edge exactly once during the BFS process. Building the reverse graph takes O(E) time, and processing all nodes takes O(V) time.
Expected Auxiliary Space Complexity: O(V + E), where O(V) is used for storing outdegree and safe arrays, and O(E) is used for storing the reverse adjacency list. The queue uses at most O(V) space.
🧑💻 Code (C++)
class Solution {
public:
vector<int> safeNodes(int V, vector<vector<int>>& edges) {
vector<int> out(V), safe(V);
vector<vector<int>> g(V);
for (auto& e : edges) out[e[0]]++, g[e[1]].push_back(e[0]);
queue<int> q;
for (int i = 0; i < V; i++) if (!out[i]) q.push(i), safe[i] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (!safe[v] && --out[v] == 0) q.push(v), safe[v] = 1;
}
vector<int> res;
for (int i = 0; i < V; i++) if (safe[i]) res.push_back(i);
return res;
}
};☕ Code (Java)
class Solution {
public ArrayList<Integer> safeNodes(int V, int[][] edges) {
int[] out = new int[V];
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < V; i++) g.add(new ArrayList<>());
for (int[] e : edges) { out[e[0]]++; g.get(e[1]).add(e[0]); }
Queue<Integer> q = new LinkedList<>();
boolean[] safe = new boolean[V];
for (int i = 0; i < V; i++) if (out[i] == 0) { q.add(i); safe[i] = true; }
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.get(u)) if (!safe[v] && --out[v] == 0) { q.add(v); safe[v] = true; }
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < V; i++) if (safe[i]) res.add(i);
return res;
}
}🐍 Code (Python)
class Solution:
def safeNodes(self, V, edges):
out, g = [0] * V, [[] for _ in range(V)]
for u, v in edges: out[u] += 1; g[v].append(u)
q, safe = [], [0] * V
for i in range(V):
if not out[i]: q.append(i); safe[i] = 1
for u in q:
for v in g[u]:
if not safe[v]:
out[v] -= 1
if not out[v]: q.append(v); safe[v] = 1
return [i for i in range(V) if safe[i]]🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated