Safe Nodes In The Graph

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
22 upvotes
Asked in companies
AmazonShareChatDeHaat

Problem statement

Ninja has been given a matrix/list 'EDGES' denoting 'E' edges of a directed graph having ‘N’ nodes. Ninja starts walking from some node (say ‘START’) in the graph along a directed edge of the graph. If Ninja reaches an end node (say ‘END’) (a node that has no outgoing directed edges), Ninja stops walking.

Now a starting node ‘START’ is a safe node only if Ninja must eventually walk to an end node ‘END’. More specifically, there must be a natural number ‘K’, so that Ninja must have stopped at an end node in less than ‘K’ steps for any choice of where to walk.

For Example: For the graph, as shown in the picture below, [2, 4] are the only safe nodes.

img

Ninja wants to know all the safe nodes in the graph in sorted order. Can you help Ninja to find out all the safe nodes?

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
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]’.
Output Format : 
For each test case, print the safe nodes in sorted order.

The output for each test case is printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
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
Sample Input 1 :
2
3 2
1 2
2 0
2 0
Sample Output 1:
0 1 2
0 1

Explanation for Sample Output 1:

For the first test case:
[0, 1, 2] are the safe nodes. See the picture below for your reference:

img

For the second case:
[0, 1] are the safe nodes. Because there is no edge between nodes so each node is a starting and an ending node.
Sample Input 2 :
2
5 3
0 1
1 0
0 2
2 2
0 1
1 0
Sample Output 2 :
2 3 4

Explanation for Sample Output 1:

For the first test case:
[2, 3, 4] are the safe nodes. See the picture below for your reference:

img

For the second test case:
There are no safe nodes. So we return an empty array/list.
Hint

Try to solve this problem iteratively.

Approaches (2)
Iterative

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.
Time Complexity

O(N + E), where ‘N’ is the number of nodes and ‘E’ is the total number of edges.

 

We are traversing each node exactly once and for each node, we are doing computation for all its connected edges. Hence overall time complexity will be O(N + E).

Space Complexity

O(N * E),  where ‘N’ is the number of nodes, and ‘E’ is the total number of edges.

 

In the worst case, the size of the queue will be ‘N’, and the size of the ‘GRAPH’ will be of order ‘N * E’.

Code Solution
(100% EXP penalty)
Safe Nodes In The Graph
Full screen
Console