# C++ 28ms BFS code that beats 100% submissions

• `````` /** Check if a circle exists in a directed graph
*  Topological sort to return a list of vertices
*  Implement Kahn's algorithm for BFS
*  Complexity O(V + E)
*/
class Graph {
int V;          // # vertices
int* indegree;  // in degree of vertices
public:
Graph(int V);
vector<int> toposort();
};

Graph::Graph(int V) {
this->V = V;
indegree = new int [V];
memset(indegree, 0, V*sizeof(int));
}

void Graph::addEdge(int u, int v) {
indegree[v]++;
}

vector<int> Graph::toposort() {
vector<int> ret(V,-1);
int retItr = V;
queue<int> q;   //queue q to store all vertices with no incoming edge
for (int i = 0; i < V; i++)
if (indegree[i] == 0)
q.push(i);
while (!q.empty()) {
int v = q.front(); q.pop(); ret[--retItr] = v;
//decrease the in degree of the vertice that is the other end of the edge
if (--indegree[*it] == 0)
q.push(*it);
}
}
if (retItr > 0) {
ret.clear();
return ret;
}// after BFS, if the grpah is still not empty, there exists at least one circle
else return ret;
}

class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
Graph g(numCourses);
for (int i = 0; i < prerequisites.size(); i++)