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
      links[x.second].insert(x.first);
      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)
      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.