Detect cycle in Directed Graph using Topological Sort | Java 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
import java . util . * ; class GFG { static int t , n , m , a ; static Stack < Integer > s ; static ArrayList < Integer > tsort ; static ArrayList < ArrayList < Integer > > adj ; static int [ ] visited = new int [ ( int ) 1e5 + 1 ] ; static void dfs ( int u ) { visited [ u ] = 1 ; for ( Integer it : adj . get ( u ) ) { if ( visited [ it ] == 0 ) dfs ( it ) ; } s . push ( u ) ; } static boolean check_cycle ( ) { Map < Integer , Integer > pos = new HashMap < > ( ) ; int ind = 0 ; while ( ! s . isEmpty ( ) ) { pos . put ( s . peek ( ) , ind ) ; tsort . add ( s . peek ( ) ) ; ind += 1 ; s . pop ( ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( Integer it : adj . get ( i ) ) { if ( pos . get ( i ) > pos . get ( it ) ) { return true ; } } } return false ; } static void addEdge ( int u , int v ) { adj . get ( u ) . add ( v ) ; } public static void main ( String [ ] args ) { n = 4 ; m = 5 ; s = new Stack < > ( ) ; adj = new ArrayList < > ( ) ; tsort = new ArrayList < > ( ) ; for ( int i = 0 ; i < 4 ; i ++ ) adj . add ( new ArrayList < > ( ) ) ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 2 ) ; addEdge ( 2 , 0 ) ; addEdge ( 2 , 3 ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( visited [ i ] == 0 ) { dfs ( i ) ; } } if ( check_cycle ( ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }