SmolBrain's blog

[Help] How to solve this DAG problem?
By SmolBrain, history, 2 years ago, In English

Problem Link

Abridged problem statement: Count the total number of distinct topological orderings of a DAG (Directed Acyclic Graph), given that each node has at most 1 incoming edge

My approach: Find an arbitrary topological ordering of the DAG using dfs and use dp to find the answer. However, I'm unable to formulate the dp states correctly.

I've hunted the entire internet for this problem's solution, but couldn't find it, so the CF community is my only hope! Please provide some hints to solve this problem.

Thanks :D

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Just some quick thoughts (not sure if correct/helpful though):

  • Let $$$dp(u) = \text{ # valid toposorts starting with u and considering only vertices that are reachable from u}$$$
  • If there is only one vertex $$$u_0$$$ with in-degree $$$0$$$ then the answer is $$$dp(u_0)$$$.
  • If we know the value of dp for all the neighbors of $$$u$$$ then we can calculate $$$dp(u)$$$ with the help of multinomial coefficients (basically we want to merge some arrays retaining the same relative order in each one).
  • If there are multiple vertices with in-degree $$$0$$$ then we can calculate the dp values for each one and then do the same as above.

Hope I helped :)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If we know the value of dp for all the neighbors of u then we can calculate dp(u) with the help of multinomial coefficients (basically we want to merge some arrays retaining the same relative order in each one).

    Can you please explain this step with much more detail?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      I'll try! Let's say (for simplicity) that $$$u$$$ has $$$2$$$ neighbors $$$u_1$$$ and $$$u_2$$$. Let $$$s_1$$$ be the number of vertices in the subtree rooted at $$$u_1$$$ (notice that the constraints are such that when we restrict ourselves to the vertices reachable from $$$u$$$ we have a directed tree rooted at $$$u$$$) and define $$$s_2$$$ similarly for $$$u_2$$$. Now say we know $$$dp(u_1)$$$ and $$$dp(u_2)$$$. How do we calculate $$$dp(u)$$$. If we have fixed orderings of the $$$s_i$$$ vertices of $$$u_i$$$ ($$$i=1,2$$$ in this case) then to produce a valid ordering of the $$$s_1 + s_2 + 1$$$ vertices of the subtree rooted at $$$u$$$ we have to place $$$u$$$ in front and then place the rest of the vertices in a way that respects the two orderings. There are $$$\binom{s_1 + s_2}{s_1}$$$ ways to do this. Do this for each of the $$$dp(u_1)\cdot dp(u_2)$$$ pairs of orderings and you get your final answer. In the general case, we just need to switch the binomial coefficient with the appropriate multinomial one.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Just a few more comments:

      • To simplify the implementation you can create a dummy vertex $$$v$$$ and connect it to all vertices with in-degree $$$0$$$. Then the answer is simply $$$dp(v)$$$.

      • You can precompute the factorials. To calculate multinomials you would need $$$\mathcal{O}(\sum \text{outdeg}(v))$$$ which is $$$\mathcal{O}(n)$$$. Therefore the total time complexity will be $$$\mathcal{O}(n)$$$.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yayy got AC! Thanks a lot for helping me solve this problem :)

        → Reply