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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int t , n , m , a ; stack < int > s ; vector < int > tsort ; vector < int > adj [ int ( 1e5 ) + 1 ] ; vector < int > visited ( int ( 1e5 ) + 1 ) ; void dfs ( int u ) { visited [ u ] = 1 ; for ( auto it : adj [ u ] ) { if ( visited [ it ] == 0 ) dfs ( it ) ; } s . push ( u ) ; } bool check_cycle ( ) { unordered_map < int , int > pos ; int ind = 0 ; while ( ! s . empty ( ) ) { pos [ s . top ( ) ] = ind ; tsort . push_back ( s . top ( ) ) ; ind += 1 ; s . pop ( ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( auto it : adj [ i ] ) { if ( pos [ i ] > pos [ it ] ) { return true ; } } } return false ; } void addEdge ( int u , int v ) { adj [ u ] . push_back ( v ) ; } int main ( ) { n = 4 , m = 5 ; 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 ( ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }