# Task Scheduling - Graph / Directed Graph / Topological Sort

not sure why this example is solved using dfs not khan’s algorithm

Yeah, very strange for solution to not solve with khan’s algorithm bfs here

it looks like it’s updated with khan’s algo

Expected output is “ok” which is incorrect.

In C#, when I ran my code, the Expected Output is showing “ok”. Please check.

Expected output is “ok” which is incorrect. Please, fix it.

What do you mean?

Thank you for pointing out. We will fix it.

Still not fixed. Should be the output itself.

from typing import List
from collections import deque

# WRITE YOUR BRILLIANT CODE HERE
#
# 1- Construct the graph
# 2- build the count of parent that will contain all parents in the graph
# 3- build the topology sort processing:
# a- Initialize the queue that expected to contain each node
# from the count of parent above.
# b- Using queue to sort the child of each node of the graph,
# put result in a list and return it

``````def count_parent(graph):
# Use of HashMap for parent counting from the graph
counts = {node:0 for node in graph}
for parent in graph:
for node in graph[parent]:
counts[node] += 1
return counts

def topo_sort(graph):

result = []
q = deque()
counts = count_parent(graph)
for node in counts:
if counts[node] == 0:
q.append(node)

while len(q) > 0:

node = q.popleft()
result.append(node)

for child in graph[node]:
counts[child] -= 1
if counts[child] == 0:
q.append(child)

return result if len(result) == len(graph) else None

graph = {t: [] for t in tasks}
for a,b in requirements:
graph[a].append(b)

``````

I am not sure if this is correct solution, but it passes all the cases

graph = defaultdict(list)

``````for pre, task in requirements:

visited = set()
return

dfs(nei)

result = []

return result
``````
``````public static List<String> taskScheduling(List<String> tasks, List<List<String>> requirements) {
Map<String, List<String>> graph = new HashMap<>();
}

for (List<String> requirement : requirements) {
}
}

private static Map<String, Integer> countParents(Map<String, List<String>> graph) {
Map<String, Integer> hm = new HashMap<>();

for (String key : graph.keySet()) {
hm.put(key, 0);
}

for (Map.Entry<String, List<String>> entry : graph.entrySet()) {
for(String node : entry.getValue()) {
hm.put(node, hm.get(node) + 1);
}
}
return hm;
}

private static List<String> topoSort(Map<String, List<String>> graph) {
List<String> result = new ArrayList<>();
ArrayDeque<String> queue = new ArrayDeque<>();

Map<String, Integer> countParents = countParents(graph);
for (Map.Entry<String, Integer> entry : countParents.entrySet()) {
if (entry.getValue() == 0)
}

while (queue.size() > 0) {
String current = queue.poll();
for (String child : graph.get(current)) {
countParents.put(child, countParents.get(child) - 1);

if (countParents.get(child) == 0) {
}
}
}
return (graph.size() == result.size()) ? result : null;
}``````

Can someone explain why the time complexity is n+m rather than n*m? Each time we pop from the cue we need to loop over all the requirements, meaning for each n (tasks) we do the full loop of m (requirements)

I didn’t use a queue in my solution, I directly deleted the keys from the card instead. It’s a bit tricky but it works very well:

``````std::map<std::string, int> count_reqs(std::vector<std::string> &tasks, std::vector<std::vector<std::string>> &requirements) {
std::map<std::string, int> res;
for (const auto &t : tasks) {
res[t] = 0;
}
for (const auto &req : requirements) {
++res[req];
}
return res;
}

std::vector<std::string> res;
std::map<std::string, int> counts = count_reqs(tasks, requirements);
while (counts.size()) {
for (std::map<std::string, int>::iterator it = counts.begin(); it != counts.end(); ) {
if (it->second == 0) {
res.push_back(it->first);
for (const auto &req : requirements) {
if (req == it->first) --counts[req];
}
counts.erase(it++);
} else
++it;
}
}
return res;
}
``````

You do not need to loop over all the requirements after you pop from the queue. You only need to loop over all the outgoing edges from the current vertex after popping that vertex from the queue, so that you can decrement the “incoming” count of each edge.

For the JS (and maybe other solutions) any reason to use a Map instead of simple object/hashmap data type, considering we don’t ever iterate over either of the maps? I feel it makes it a lot less readable to use Map, so prefer object if there’s not a meaningful performance difference.

Here’s a solution with objects that seems more readable to me:

``````function taskScheduling(tasks, requirements) {
const inDegrees = {};
const dependents = {};

}

for (let i = 0; i < requirements.length; i++) {
const parent = requirements[i];
const child = requirements[i];
inDegrees[child] += 1
dependents[parent].push(child)
}

const q = [];
}
}

const ans = [];
while (q.length > 0) {