Блог пользователя SmolBrain

[Help] How to solve this DAG problem?
Автор SmolBrain, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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 :)

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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)$$$.

      → Ответить