Topological Sort

// Topological Sort
using namespace std;

class TopologicalSort {
 public:
  static vector<int> sort(int vertices, const vector<vector<int>>& edges) {
    vector<int> sortedOrder;
    unordered_map<int, int> inDegree;
    unordered_map<int, vector<int>> graph;
    queue<int> sources;

    for (int i = 0; i < vertices; i++) {
      inDegree[i] = 0;
      graph[i] = vector<int>();
    }

    for (int i = 0; i < edges.size(); i++) {
      int parent = edges[i][0];
      int child = edges[i][1];

      inDegree[child]++;
      graph[parent].push_back(child);
    }

    for (int i = 0; i < vertices; i++) {
      if (inDegree[i] == 0) {
        sources.push(i);
      }
    }

    cout << "sources [0] = " << sources.front();

    while (!sources.empty()) {
      int s = sources.front()
      sources.pop();
      sortedOrder.push_back(s);
      for (auto e : graph[s]) {
        inDegree[e]--;
        if (inDegree[e] == 0) {
          sources.push(e);
        }
      }
    }

    if (sortedOrder.size() != vertices) {
      return vector<int>();
    }

    return sortedOrder;
  }
};


// Find out if tasks could be scheduled

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

class TaskScheduling {
 public:
  static bool isSchedulingPossible(int vertices, const vector<vector<int>>& edges) {
      unordered_map<int, int> outDegree;
      unordered_map<int, vector<int>> graphInDegree;
      queue<int> sinks;
      vector<int> sortedOrder;

      for (int i = 0; i < vertices; i++) {
        outDegree[i] = 0;
        graphInDegree[i] = vector<int>();
      }

      for (int i = 0; i < edges.size(); i++) {
        int parent = edges[i][0];
        int child = edges[i][1];
        outDegree[parent]++;
        graphInDegree[child].push_back(parent);
      }

      for (int i = 0; i < vertices; i++) {
        if (outDegree[i] == 0) {
          sinks.push(i);
        }
      }

      while (!sinks.empty()) {
        int s = sinks.front();
        sinks.pop();
        sortedOrder.push_back(s);
        for (auto e : graphInDegree[s]) {
          outDegree[e]--;
          if (outDegree[e] == 0) {
            sinks.push(e);
          }
        }
      }

      return sortedOrder.size() == vertices;
  }
};