There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of node a is strictly greater than value of node b. What is the total number of combinations of assigning natural numbers as node values such that value of any node is between 1 to C ?

  • 1
    $\begingroup$ Still, you use the word "component" incorrectly. The total number of combinations depends on the graph itself. For example, if $c = \text{the number of nodes}$, then the total number of combinations is bounded from below by the total number of topological orderings of the graph. $\endgroup$ Commented Jan 27 at 13:13
  • 2
    $\begingroup$ What kind of answer are you looking for? An algorithm to compute this number? Any algorithm at all, or do you have some restrictions on running time? An upper bound on this number? A lower bound? Something else? What's the context in which you encountered this problem? Can you credit the original source? Can you describe the motivation? I encourage you to edit your post to state your question more clearly. $\endgroup$
    – D.W.
    Commented Jan 28 at 6:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.