Leetcode problem on cycle

#1

problem link>>

I am getting TLE Can u plz help me to solve it

#2

hello @joshisanjay8467

a)
pass ur vector v by reference

b)

ss
ss729×149 11.1 KB

here this make dfs qudratic.

c) hint-> top sort ? with bfs it will be easy

#3

bhaiya in interview dfs is going to strike first for this ques. and I saw most of the people used dfs only can u suggest some optimizations to get out of tle I am using the graph vector only but still getting TLE
UPDATED CODE > https://ide.codingblocks.com/s/480760

#4

…

discard that loop from the dfs keep track of three things to optimise it furthur.
its more like memoisation
a) visited node (nodes that are already visited)
b) safe node (nodes that are already safe , intilally it will be empty)
c) cylce node (nodes that are ended in some cycle ,initially it will be empty)

run ur ususal dfs

bool dfs(src) {
 
  if(src is already present in safe set) return true

  if(src is already presnet in cycle set) return false
  
if(src is visited before)   { //it means cycle
    cycle.insert(src) //insert in cyclic node

    return false;
    }
insert in visited set
for( all neighbours of src ) {
    
        if(dfs(neigbour)==false) { means neigbour going in cycle ,hence src will too go in cycle

            put src in cycle set and retunr false
          }


}
 
loop executed successfully that means src is not going to any  cycle so
put it in safe nodes set
and return true;

call dfs for all nodes and if it returns true put that node in ur ans vector
}

#5

thankyou bhaiya solved it !!

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.