CareerCup

My answer:
Well the idea is to 1st process all node whose in-degree is 0. Then keep processing newly added nodes whose in-degree becomes 0. The main part is coming up with a parallel solution.

Algorithm:
- Dedicate a process to go through the graph and add ready nodes (whose in-degree is 0) to a ready-process-queue
- Either use SMP or Master-Slave architecture to assign processing of each node present in the ready queue.
- For efficient tracking of changing in-degrees, maintain a hash<nodeID,indegreeCount>, which is updated for all the outDegree nodes of the currently processed node. Say if we have a link A->B. When processing A we can decrement the indegree count of B.
- Few enhancements are the main process which scans the graph for 0 indegree nodes can be designed to receive a signal when new nodes are ready (whose in-degree has become 0) rather than staying in a busy-wait loop.

Topological sort can do it. I dont know how to make it parallel ?

if i've understood question well, we have some kind network planing. So we need to know which parts of job can be done in parallel. We can do BFS on the graph and mark vertexes. Those vertexes who are on the same level - can be proceed in parallel. But how to find distinct branches, who can be proceed independently - i have no ideas.