An interesting and simple way to find the existence of cycles in a directed graph is using Kahns algorithm for topological sort.

typedef struct{intv; // end vertexintw; // weight of edge } Edge;intN; // No of verticesintn_edges; // No of edges vector< vector< Edge > > adjlist; // Graph represented as an adjacency list vector<int> isolated_vert; // List of isolated vertices having indegree 0intindegree[N]; // Populate with indegree of every vertexintcur_vert, sz;while(isolated_vert.size() != 0) { cur_vert = isolated_vert[0]; sz = adjlist[cur_vert].size();for(inte = 0; e < sz; e++) { /* Remove all outgoing edges */ indegree[ adjlist[cur_vert][e].v ] -= 1; n_edges -= 1; /* If vertex has indegree 0 add to list of isolated vertices */if(indegree[adjlist[cur_vert][e].v] == 0) { isolated_vert.push_back( adjlist[cur_vert][e].v ); } } isolated_vert.erase(isolated_vert.begin()); } /* Graph still has edges */if(n_edges > 0) { cout<< "Cycle found" << endl; }elsecout<< "No Cycle found" << endl;

The total time complexity is O(|V| + |E|)

Advertisements