[–] [deleted] 0 points 1 points (+1|-0) ago 

[Deleted]

0
0

[–] katara [S] 0 points 0 points (+0|-0) ago 

Neat! I've never seen scheme code before. :) It vaguely looks like you systematically (recursively, in "topological_sort") find items with zero dependencies and remove them from the dependencies list (and add them to the job queue) until there's nothing left?

I wonder what the running time is. I think O(e*k) where e = # dependencies and k = job with most dependencies?

[–] [deleted] 0 points 1 points (+1|-0) ago  (edited ago)

[Deleted]

0
0

[–] katara [S] 0 points 0 points (+0|-0) ago 

Cool! I'm guessing instead of straight up finding strongly connected components you're outputting answers when you hit a node with no outbound edges?

That's more or less what I was thinking too. Except since you're given a hashmap you could also iterate across the keys of the map in a depth-first search manner, recursively searching for jobs with no dependencies to run and marking visited jobs/nodes to keep the running time linear in terms of number of dependencies :)