Safe Nodes In The Graph
Posted: 31 Mar, 2021
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.
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?
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]’ and ‘EDGES[i]’ which is a directed edge from node ‘EDGES[i]’ to ‘EDGE[i]’.
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.
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] and EDGE[i] < N Where ‘EDGE[i]’ and ‘EDGE[i]’ represents the directed edge. Time Limit: 1 sec