I have a DAG where an edge represents a dependency between two nodes and a node represents a task that is to be executed on a machine. There are multiple machines. For each (task,machine) pair there is an estimated runtime. Now, I would like to separate this DAG into a forest so that each subgraph in the forest represents itself a "complete" DAG and is represented by a topological level ordered sorting. By "complete" I mean that the subgraph starting from any root node has exactly all the paths that it has in the original DAG. I am given an unordered List<Task> tasks where Task is a class that represents a task node in the DAG. Every Task has a List of all its parents and a List of all its children. How I would naively go about: iterate over all the nodes v, do a dfs to get the subgraph rooted at v, in each iteration check if one can merge two subgraphs because they have a common parent. Can this be done faster?

CodePudding user response：

Separate the graph into components using a depth-first search which traverses both child and parent links. Then you can do a topological sort on each component. Both algorithms are O(N E) (for N nodes and E edges); that could be O(N²) but for typical dependency graphs where the number of dependencies is generally small, it's probably closer to O(N).