Detect cycle in Directed Graph using Topological Sort | C # 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static int n ; static Stack < int > s ; static ArrayList tsort ; static ArrayList adj ; static int [ ] visited = new int [ 100001 ] ; static void dfs ( int u ) { visited [ u ] = 1 ; foreach ( int it in ( ArrayList ) adj [ u ] ) { if ( visited [ it ] == 0 ) dfs ( it ) ; } s . Push ( u ) ; } static bool check_cycle ( ) { Dictionary < int , int > pos = new Dictionary < int , int > ( ) ; int ind = 0 ; while ( s . Count != 0 ) { pos . Add ( s . Peek ( ) , ind ) ; tsort . Add ( s . Peek ( ) ) ; ind += 1 ; s . Pop ( ) ; } for ( int i = 0 ; i < n ; i ++ ) { foreach ( int it in ( ArrayList ) adj [ i ] ) { if ( pos [ i ] > pos [ it ] ) { return true ; } } } return false ; } static void addEdge ( int u , int v ) { ( ( ArrayList ) adj [ u ] ) . Add ( v ) ; } public static void Main ( string [ ] args ) { n = 4 ; s = new Stack < int > ( ) ; 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 ( ) ) Console . WriteLine ( " Yes " ) ; else Console . WriteLine ( " No " ) ; } }