A 480 ms C++ solution, BFS

  • 0

    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)
      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])
      if (j >= n)
      return null;
      inedge[j] = -1; //'delete' the current node (this node will no be chosen anymore)
      for (int x : links[j])
      --inedge[x]; //remove current node's outgoing edges
      return ret;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.