# A 480 ms C++ solution, BFS

• The idea is come from wiki: https://en.wikipedia.org/wiki/Topological_sorting#Algorithms

and many thanks for @jianchao.li.fighter's brillant solution.

Two key point of Topological sorting is:

1. Build the map and relationship of each node (incoming and outgoing edges of each node).

2. Each time remove a node that with no incoming edges and at same time remove this node's outgoing edges.

vector<int> findOrder(int n, vector<pair<int, int>>& pre)
{
vector<int> ret;
vector<int> null;
vector<unordered_set<int>> links(n); //As there are n courses, use index of array to represent each node
vector<int> inedge(n, 0);
for (auto x : pre) //convert pair<int, int> into nodes' relation map
for (auto x : links) //calculate incoming edges of each node.
{
for (int y : x)
++inedge[y];
}
int i, j;
for (i = 0; i < n; ++i) //search for n times. If all courses can be taken, all nodes should be 'removed'
{
for (j = 0; j < n; ++j) //search for a node with no incoming edges
{
if (0 == inedge[j])
break;
}
if (j >= n)
return null;
ret.push_back(j);
inedge[j] = -1; //'delete' the current node (this node will no be chosen anymore)