toposort checking cycle on own: Credit to Ruichao

toposort.cpp

//@Author : Ruichao Chen

int V; 			// number of vertices
vector<int> adj[1000];  // adjacency list (adj[u] is list of successors of u)

int degree[1000];	// number of edges pointing to u
vector<int> sorted;
bool toposort() {
	for (int u = 0; u < V; u++) {
		int sz = adj[u];
		for (int i = 0; i < sz; i++) {
			int v = adj[u][i];
			degree[v]++;
		}
	}
	queue<int> Q;
	for (int u = 0; u < V; u++)
		if (degree[u] == 0)
			Q.push(u);
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		sorted.push_back(u);
		int sz = adj[u].size();
		for (int i = 0; i < sz; i++) {
			int v = adj[u][i];
			degree[v]--;
			if (degree[v] == 0)
				Q.push(v);
		}
	}
	if (sorted.size() < V) {
		cerr << "Sorry, this is not a DAG" << endl;
		return false;
	}
	cerr << "DAG sorted. Results:";
	for (int i = 0; i < (int)sorted.size(); i++)
		cerr << ' ' << sorted[i];
	cerr << endl;
	return true;
}

int main() {
	read_input_blah_blah();
	if (toposort()) {
		do_something_with_sorted_array_blah_blah();
	} else {
		complain_about_non_DAG_blah_blah();
	}
	some_more_blahs();
	return 0;
}
http://pastebin.ubuntu.com/23547745/