New update is available. Click here to update.

Last Updated: 31 Mar, 2021

Difficulty: Moderate

```
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The first line of each test case contains an integer ‘N’ and ‘E’ representing the number of nodes and edges in the graph.
The next ‘E’ lines of each test case contain two single space-separated integers denoting ‘EDGES[i][0]’ and ‘EDGES[i][1]’ which is a directed edge from node ‘EDGES[i][0]’ to ‘EDGE[i][1]’.
```

```
For each test case, print the safe nodes in sorted order.
The output for each test case is printed in a separate line.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= E <= 10 ^ 4
0 <= EDGE[i][0] and EDGE[i][1] < N
Where ‘EDGE[i][0]’ and ‘EDGE[i][1]’ represents the directed edge.
Time Limit: 1 sec
```

The idea behind this approach is we try to find if there is a cycle from the node we start. If we are able to find it, then we will mark that node and remove it, and if we cannot reach it, then after some number of steps, we'll stop.

A node will be ultimately safe if all of its outgoing edges to nodes are safe.

We start with the nodes with zero outgoing edges, which are already safe.

We can consider any node which is only pointing to safe nodes.

Then, we can update those nodes again, and so on, we do this for all the nodes.

Here is the complete algorithm:

- We will make a matrix/list ‘GRAPH’ using the given array/list ‘EDGES’.
- Insert all ‘EDGES[i][1]’ at index ‘EDGES[i][0]’ of the ‘GRAPH’.

- Make a queue 'QUE', an array/list ‘SAFE’ of size ‘N’ and arrays/lists ‘GRAPH1’ and ‘GRAPH2’ of type HashSet because the insertion and deletion operation in HashSet is of order O(1).
- ‘GRAPH1’ will store edges from ‘i’ to ‘j’.
- ‘GRAPH2’ will store edges from ‘j’ to ‘i’.

- Run a for loop from ‘i’ = 0 to ‘N’ and for each ‘i’ do the following:
- If the size of ‘GRAPH1[i]’ is zero. Then add ‘i’ to the 'QUE'.
- Traverse all the neighbors of the node ‘i’ do the following:
- Add neighbor to the ‘GRAPH1[i]’.
- Add node ‘i’ to the ‘GRAPH2[j]’.

- While 'QUE' is not empty do the following:
- Pop the node ‘temp’ from the 'QUE' and mark it visited.
- Traverse all the neighbors of the ‘temp’ in ‘GRAPH2’ and do the following:
- Remove the ‘temp’ node from the ‘GRAPH1’.
- If the size of ‘GRAPH1[neighbor]’ is zero
- Add neighbors to the 'QUE'.

- Traverse the ‘SAFE’ array/list if ‘SAFE[i]’ is true then include it in the final answer.

The idea behind this approach is the same as discussed in the previous approach but this time we use DFS to find the cycle in the graph. If we encounter the node for the first time we mark it visited and assign 1 to it. If we encounter a node that is already processed i.e: is assigned 1 means there is a cycle and we will not include those nodes in our answer.

Here is the complete algorithm:

- We will make an array/list ‘GRAPH’ using the given array/list ‘EDGES’.
- Insert all ‘EDGES[i][1]’ at index ‘EDGES[i][0]’ of the ‘GRAPH’.

- We will traverse each node in the ‘GRAPH’ and for each node, we will call the ‘
**DFS**’ function which has an array/list ‘VISITED’, ‘CURRENT_NODE’, and ‘GRAPH’. - If the node is not processed we call our ‘
**DFS**’ function do the following:- Mark the ‘CURRENT_NODE’ visited i.e: ‘VISITED[CURRENT_NODE]’ = 1.
- Traverse all the neighbors of ‘CURRENT_NODE’ and do the following:
- If ‘VISITED[NEIGHBOUR]’ is 0 and ‘
**DFS(GRAPH, VISITED, NEIGHBOUR)**’ gives true then we return true. - If ‘VISITED[NEIGHBOUR]’ is 1 then return true.

- If ‘VISITED[NEIGHBOUR]’ is 0 and ‘
- Mark it visited i.e: ‘VISITED[CURRENT_NODE]’ = 2.

- If the ‘
**DFS**’ function returns false then we add the node in our answer. - Finally, we return the answer.

SIMILAR PROBLEMS

Plantation

Posted: 9 Sep, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Capturing Grid

Posted: 14 Sep, 2022

Difficulty: Moderate

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: