Complexities:
TC: O(V+E)
SC: O(1)
vector<int> topoSort(int N, vector<int> adj[]){ // topological sort // N = number of vertices in graph // adj = adjacency list
queue<int> q; // queue of vertices with no incoming edges
vector<int> inDegree(N,0); // inDegree[i] = number of incoming edges to vertex i
for(int i=0;i<N;i++){
for(auto it:adj[i]){ // for each edge (i,j) in graph // it = j in this case
inDegree[it]++; // inDegree[i] = # of edges that point to i
}
}
for(int i=0;i<N;i++){
if(inDegree[i]==0){ // if there is no edge pointing to i
q.push(i);
}
}
vector<int> topo;
while(!q.empty()){ // while there is still a node with no incoming edges
int curr = q.front();
q.pop(); // remove the node from the queue
topo.push_back(curr); // add the node to the topo vector
for(auto it:adj[curr]){ // for each node that points to curr
inDegree[it]--; // decrement the inDegree of that node
if(inDegree[it]==0){ // if the inDegree of that node is 0
q.push(it); // add it to the queue
}
}
}
return topo; // return the topo vector
}