Detect cycle in Directed Graph using Topological Sort | Python3 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
t = 0 NEW_LINE n = 0 NEW_LINE m = 0 NEW_LINE a = 0 NEW_LINE s = [ ] NEW_LINE tsort = [ ] NEW_LINE adj = [ [ ] for i in range ( 100001 ) ] NEW_LINE visited = [ False for i in range ( 100001 ) ] NEW_LINE def dfs ( u ) : NEW_LINE INDENT visited [ u ] = 1 NEW_LINE for it in adj [ u ] : NEW_LINE INDENT if ( visited [ it ] == 0 ) : NEW_LINE INDENT dfs ( it ) NEW_LINE DEDENT DEDENT s . append ( u ) NEW_LINE DEDENT def check_cycle ( ) : NEW_LINE INDENT pos = dict ( ) NEW_LINE ind = 0 NEW_LINE while ( len ( s ) != 0 ) : NEW_LINE INDENT pos [ s [ - 1 ] ] = ind NEW_LINE tsort . append ( s [ - 1 ] ) NEW_LINE ind += 1 NEW_LINE s . pop ( ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT for it in adj [ i ] : NEW_LINE INDENT first = 0 if i not in pos else pos [ i ] NEW_LINE second = 0 if it not in pos else pos [ it ] NEW_LINE if ( first > second ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def addEdge ( u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE m = 5 NEW_LINE addEdge ( 0 , 1 ) NEW_LINE addEdge ( 0 , 2 ) NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 2 , 0 ) NEW_LINE addEdge ( 2 , 3 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( visited [ i ] == False ) : NEW_LINE INDENT dfs ( i ) NEW_LINE DEDENT DEDENT if ( check_cycle ( ) ) : NEW_LINE INDENT print ( ' Yes ' ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ' No ' ) NEW_LINE DEDENT DEDENT