Time Cost

30min57s

Implementation

Using Kahn’s algorithm which keeps removing nodes without dependencies from the graph. If the graph is a DAG(Directed Acyclic Graph), there must be new nodes without any dependencies once removing a node.

Next we should move on how to find the node without any dependencies. We can maintain a priority queue with nodes and their indegrees(dependencies). Once its indegree becomes zero, we can refer that this node doesn’t have any dependencies left and could be candidated as the node to be removed.

Until now, we can build up our own solution. As shown in solution 1, we got a intuitive implementation with bad time complexity (O(V^2 + E)) which Kahn’s algorithm should be in O(V+E). We can optimize a little bit as shown in Solution 2. The main difference is that we don’t have to scan every node in each loop. We can simply do the scanning while doing the deduction on indegree vector.

Code

  • Solution 1 
    class Solution {
public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      queue<int> qu;
      unordered_map<int, vector<int>> dependencies;
      vector<int> indegree(numCourses, 0);
      vector<int> result;
      for (vector<int>& p: prerequisites) {
          indegree[p[0]]++;
          dependencies[p[1]].push_back(p[0]);
      }

      // here, we got a priority queue with min heap (the node with the least dependency)
      // if this is a DAG, the least means zero dependency
      int count = numCourses;
      while (count > 0) {
          // 1. add indegree=0 nodes into queue & mark removed node indegree=-1
          for (int i=0; i<numCourses; i++) {
              if (indegree[i] == 0) {
                  qu.emplace(i);
                  indegree[i] = -1;
              }
          }

          if (qu.empty()) {
              // impossible, it's not a DAG
              return {};
          }

          // 2. pop one node each time & update indegree
          while (!qu.empty()) {
              int removed = qu.front();
              qu.pop();
              vector<int> dependency = dependencies[removed];
              for (int i: dependency) {
                  indegree[i]--;
              }
              count--;
              result.push_back(removed);
          }
      }
        
      return result;
  }
};
  • Solution 2 
    class Solution {
public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      vector<vector<int>> graph(numCourses);
      vector<int> indegree(numCourses, 0);

      for (auto& p : prerequisites) {
          int a = p[0], b = p[1];
          graph[b].push_back(a);
          indegree[a]++;
      }

      queue<int> q;
      for (int i = 0; i < numCourses; ++i)
          if (indegree[i] == 0) q.push(i);

      vector<int> result;
      result.reserve(numCourses);

      while (!q.empty()) {
          int u = q.front(); 
          q.pop();
          result.push_back(u);

          for (int v : graph[u]) {
              if (--indegree[v] == 0) q.push(v);
          }
      }

      if (result.size() != numCourses) return {};
      return result;
  }
};

Reference