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.
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.
Each graph[i] contains the edges of the node in graph[i].
In example 1,
Path 1:
From 0th vertex, there are two edges [1, 2]. As we are going to traverse in DFS, let's take edge 1. From vertex 1, there are two edges [2, 3]. Similarly, we are taking first edge which is 2. From vertex 2, we are taking edge 5 and vertex 5, doesn't have any edges. so it gets terminated.
Hence, vertex 5 and 2 are marked as safe node.
Path 2 :
If we consider the path 0->1->3->0, it will form a cycle but not lead to terminal node. Hence, 0, 1, and 3 are not safe node.
From 0th vertex, there are two edges [1, 2]. As we are going to traverse in DFS, let's take edge 1. From vertex 1, there are two edges [2, 3]. We are going to taking second edge which is 3 because first edge is already visited. From vertex 3, it leads to already visited vertex/node which is 0. This means it is forming a circle. Hence 3 is not a safe node. Also, 3's parent 0 is also not a safe node.
Path 3: But, if we consider other path 0->2->5, it will lead to terminal node. So, 2 is a safe node.
Path 4:
Similarly, the path from 4 to 5 is safe node as 4 leads only to 5. So, all the neighbours of 4 is safest.
Path 6:
As 6 doesn't have any edge, it is going to be a safe node.
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.
From this example [[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]
Path 1:
From 0th vertex, there are four edges [1, 2, 3, 4]. As we are going to traverse in DFS, let's take edge 1. From vertex 1, vertex 1 is marked as visited node, and there are two edges [1, 2]. Similarly, we are taking first edge which is 1. At this point, vertex 1 is already visited, so this creates a cycle. So, vertex 1 is marked as cycle node and vertex 0 which is parent of vertex 1 also marked as cycle node. So, both nodes are not safe node.
Path 2 :
Let's take path from vertex 2 which has two edges [3, 4]. Considering DFS, edge 3 is taken. Vertex 3 has two edges [0, 4]. As 0 is visited already, it forms a cycle. This means vertex 2 parent is leading to cycle. So, both nodes 2 and 3 are not safe node.
Path 3: As there are no outgoing edges from vertex 4, it is a safe node.
Constraints:
n == graph.length
1 <= n <= 104
0 <= graph[i].length <= n
0 <= graph[i][j] <= n - 1
graph[i]
is sorted in a strictly increasing order.- The graph may contain self-loops.
- The number of edges in the graph will be in the range
[1, 4 * 104]
.
We can do this in O(E+V) complexity because we will not visit the node or edges which are visited already.
Note that recursion function should be invoked only for the non-visited nodes or non-explored nodes.
class Solution { private: bool detectCycle(vector<vector<int>>& graph, vector<int>& state, int node) { state[node] = 1; for (auto& adjnode : graph[node]) { //cout << "Node has edges " << node << " adjnode " << adjnode << endl; if (state[adjnode] == 0) { if (detectCycle(graph, state, adjnode)) { //cout << "Parent Node also forms cycle " << node << " adjnode " << adjnode << endl; return true; } } else if(state[adjnode] != 2) { //cout << "Child node " << adjnode << " of parent " << node << " got visited already " << endl; return true; } //cout << "Next edge for " << node << " adjnode " << adjnode << endl; } //cout << "Safe node " << node << endl << endl; state[node] = 2; return false; } public: vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n = graph.size(); vector<int> state(n, 0); for (int i=0; i<n; i++) { if (state[i] == 0) { //cout << "Non-visited node " << i << endl; detectCycle(graph, state, i); } } vector<int> safeNodes; for (int i=0; i<n; i++) { if (state[i] == 2) { safeNodes.push_back(i); } } return safeNodes; } };
Comments
Post a Comment