Detect cycle in Directed Graph using Topological Sort | JavaScript Program to implement the above approach ; Stack to store the visited vertices in the Topological Sort ; Store Topological Order ; Adjacency list to store edges ; To ensure visited vertex ; ( Function to perform ) DFS ; Set the vertex as visited ; Visit connected vertices ; Push into the stack on complete visit of vertex ; Function to check and return if a cycle exists or not ; Stores the position of vertex in topological order ; Pop all elements from stack ; Push element to get Topological Order ; Pop from the stack ; If parent vertex does not appear first ; Cycle exists ; Return false if cycle does not exist ; Function to add edges from u to v ; Driver Code ; Insert edges ; If cycle exist
var t , n , m , a ; var s = [ ] ; var tsort = [ ] ; var adj = Array . from ( Array ( 100001 ) , ( ) => Array ( ) ) ; var visited = Array ( 100001 ) . fill ( 0 ) ; function dfs ( u ) { visited [ u ] = 1 ; adj [ u ] . forEach ( it => { if ( visited [ it ] == 0 ) dfs ( it ) ; } ) ; s . push ( u ) ; } function check_cycle ( ) { var pos = new Map ( ) ; var ind = 0 ; while ( s . length != 0 ) { pos . set ( s [ s . length - 1 ] , ind ) ; tsort . push ( s [ s . length - 1 ] ) ; ind += 1 ; s . pop ( ) ; } var ans = false ; for ( var i = 0 ; i < n ; i ++ ) { adj [ i ] . forEach ( it => { if ( ( pos . has ( i ) ? pos . get ( i ) : 0 ) > ( pos . has ( it ) ? pos . get ( it ) : 0 ) ) { ans = true ; } } ) ; } ; return ans ; } function addEdge ( u , v ) { adj [ u ] . push ( v ) ; } n = 4 , m = 5 ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 2 ) ; addEdge ( 2 , 0 ) ; addEdge ( 2 , 3 ) ; for ( var i = 0 ; i < n ; i ++ ) { if ( visited [ i ] == 0 ) { dfs ( i ) ; } } if ( check_cycle ( ) ) document . write ( " " ) ; else document . write ( " " ) ;