There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Example 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6] Explanation: The given graph is shown above. Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them. Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
Example 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] Output: [4] Explanation: Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.
Constraints:
n == graph.length1 <= n <= 1040 <= graph[i].length <= n0 <= graph[i][j] <= n - 1graph[i] is sorted in a strictly increasing order.[1, 4 * 104].In #802 Find Eventual Safe States, you are given a directed graph and must determine which nodes are eventually safe, meaning every path starting from them eventually leads to a terminal node rather than a cycle. The key insight is that unsafe nodes are those that are part of a cycle or can reach one.
A common strategy is using Depth-First Search (DFS) with node coloring or state tracking. During traversal, if a node is revisited in the current recursion stack, it indicates a cycle, marking it unsafe. Nodes that successfully finish DFS without encountering a cycle are considered safe.
Another efficient method is using topological sorting with BFS. By reversing the graph and starting from terminal nodes (nodes with no outgoing edges), you iteratively remove safe nodes and reduce the outdegree of their predecessors. Nodes that eventually reach zero outgoing edges become safe.
Both approaches efficiently process the graph in O(V + E) time, where V is the number of nodes and E is the number of edges.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with cycle detection | O(V + E) | O(V) |
| BFS with reverse graph (Topological Sort) | O(V + E) | O(V + E) |
take U forward
This approach utilizes the concept of reversing the graph and then performing a topological sort. Essentially, if we consider nodes leading to terminal nodes in the original graph, these nodes can be treated as terminal nodes in the reversed graph. We perform a topological sort to find such nodes.
By processing nodes which have no outgoing edges in the reversed graph (these correspond to safe nodes in the original graph), we can iteratively determine more nodes that are safe.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal.
Space Complexity: O(V) for storing the reversed graph and the in-degrees array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5void findEventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize) {
6 // Implementation
7}
8
9int main() {
10 int n = 7;
11 int graphColSize[] = {2, 2, 1, 1, 1, 0, 0};
12 int graphData[7][2] = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
13 int* graph[7];
14 for (int i = 0; i < 7; i++) {
15 graph[i] = graphData[i];
16 }
17 int returnSize = 0;
18 findEventualSafeNodes(graph, 7, graphColSize, &returnSize);
19 return 0;
20}The function findEventualSafeNodes reverses the input graph and employs a topological sorting method to determine the safe nodes.
For simplicity, you will need to manage node degrees and process the graph using a queue (BFS style). Nodes that have no incoming edges left are safe.
This approach adopts a classic depth-first search (DFS) to identify which nodes are safe. Safe nodes are marked during traversal.
We maintain a visited state for each node: unvisited, visiting, or safe. During DFS traversal, if we encounter a node marked as visiting, a cycle is detected, and the path is unsafe.
Time Complexity: O(V + E), as each node and each edge is examined only once.
Space Complexity: O(V) for the recursion stack and state storage.
1#include <vector>
2#include <iostream>
3using namespace std;
4
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
// Implementation
return {};
}
int main() {
vector<vector<int>> graph = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
vector<int> result = eventualSafeNodes(graph);
for (int node : result) {
cout << node << " ";
}
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, graph problems involving cycle detection, DFS, and topological sorting are common in FAANG-style interviews. This problem tests your understanding of graph traversal and reasoning about cycles and terminal states.
Adjacency lists are typically used to represent the graph efficiently. For the BFS topological approach, additional structures like a queue and arrays for tracking outdegree or node states are commonly used.
The optimal approaches are DFS with cycle detection or BFS using topological sorting on a reversed graph. Both methods identify nodes that eventually lead to terminal nodes and avoid cycles. Each runs in O(V + E) time, making them efficient for large graphs.
Reversing the graph allows you to start from terminal nodes and propagate safety backward. By reducing the outdegree of predecessor nodes, you can identify which nodes eventually lead only to safe nodes.
The function leverages DFS to maintain a status for each node: safe, unsafe, or unknown. It handles cycles efficiently by marking nodes actively being visited and recording safe nodes on successful completion of DFS for a node.