Detecting cycles using topological sort

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

typedef struct 
	int v; // end vertex
	int w; // weight of edge
} Edge;

int N; // No of vertices
int n_edges; // No of edges

vector< vector< Edge > > adjlist; // Graph represented as an adjacency list
vector< int > isolated_vert; // List of isolated vertices having indegree 0

int indegree[N]; 	// Populate with indegree of every vertex
int cur_vert, sz; 

while(isolated_vert.size() != 0)
    cur_vert = isolated_vert[0];
    sz = adjlist[cur_vert].size();

    for(int e = 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 );
/* Graph still has edges */
if(n_edges > 0)
	cout<< "Cycle found" << endl; 
else cout<< "No Cycle found" << endl;

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


Passing extra parameters to STL sort

While attempting to solve a Quora challenge , I had the necessity to sort a vector of objects with a third parameter as a reference.

My vector looked like

class Topic;
class Query;

vector<Topic> list_topics;

I needed to sort the vector list_topics using a Query object as reference. But traditionally, a comparator function takes in only 2 arguments of the same type as the elements that are being sorted.

bool compareTopics(const Topic t1 , const Topic t2){}; // Traditional comparator
sort( list_topics.begin() , list_topics.end() , compareTopics);

I needed to pass in a third parameter to make it,

bool compareTopics(const Topic t1, const Topic t2, Query query){
// compare here

In order to do this, we need to make use of functors i.e an object that can be called like a regular function. To implement this in C++, we need to define a class and implement to () operator function, while passing the extra arguments we need to the class constructor.

class TopicSorter{
    Query query_;
    TopicSorter(Query query){ query_ = query; }
    bool operator()(Topic t1, Topic t2) const {
    return compareTopics( t1 , t2 , query_);

Now we can sort the vector of objects

Query query;
sort(list_topics.begin() , list_topics.end() , TopicSorter(query));