How to find all topological sortings of a special DAG in O(N^2)

I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.

https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum

Problem description:

Nikita has a family tree $$T$$ consisting of $$N$$ members number from $$1$$ to $$N$$. Each of the $$N-1$$ edges in the tree represents a directed relationship. Basically if there is an edge from member $$A$$ to $$B$$, it means $$B$$ was born before $$A$$. Now, Nikita knows that these $$N$$ members were born in last $$M$$ days and only $$1$$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $$N$$ family members.

Since the required answer can be quite large, print it modulo $$10^9+7$$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $$T$$.

Let randomly root the tree $$T$$ at any node say $$1$$. Lets calculate a $$dp(i, j)$$ denoting the number of topological sorts of subtree rooted at $$i^{th}$$ node such that $$i^{th}$$ node is placed at position. Assume that there are $$X$$ outgoing edges to the children from and $$Y$$ incoming edges. Note that all the $$X$$ children has to be placed on the left and all the $$Y$$ children has to be placed on the right side of $$i^{th}$$ in a valid topological sort.

Now lets calculate another $$dp(i, j)$$ for those $$X$$ nodes. Similiarly, we will do for $$Y$$ nodes. Here $$dp(i, j)$$ denotes the number of ways of filling $$j$$ spaces using topological sorts of subtrees rooted at $$X_1, X_2, \cdots X_i$$ such that $$X_1, X_2, \cdots X_i$$ is placed in $$j$$ spaces. Note that to compute this $$dp$$, we can use the $$DP$$ already calculated at these children nodes.

$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$

Note that this $$\sum_{1\le l \le k} DP(i, l)$$ is just a prefix sum and can be precomputed.

Now, for $$X$$ nodes basically you have computed $$dp_j$$, number of filling up $$j$$ spaces using subtrees of $$X$$ nodes such that $$X_1, X_2, \cdots X_x$$ is included. Lets call this $$dp$$ as $$left[]$$ and similary call the $$dp$$ for $$Y$$ nodes as $$right[]$$.

$$DP(i, j) = \sum_{1\le k < j} nCr(j-1, k) \times {left}_k \times nCr(a, b) \times {right}_{a-b}$$

Where $$a = SZ_i - j$$, $$b = SZ_x - k$$ and $$SZ_i$$ denotes the size of subtree rooted at $$i^{th}$$ node & $$SZ_x$$ denotes the sum of sizes of all subtrees rooted at all those $$X$$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $$O(N^2)$$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.

I believe that the added constraint that the number of edges is equal to $$N-1$$ simplifies the solution, and I couldn't think of any other possibility.

Could anyone kindly validate the solution?

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.

• The formula that you have given works only for trees in which EVERY NODE HAS ONLY ONE PARENT. However, in this case, there could be multiple parents of a single node. I think what the question-setter means by trees is that there is at most one directed path between any two nodes. There is a test case in which a node is shown to have multiple parents. Sep 13 '18 at 14:30

The provided editorial is so hard to read. My solution is similar (or not?) to the provided one, but easier to understand.

Let $$dp(u, i)$$ be the number of topological sorts of subtree rooted at node $$u$$ such that node $$u$$ is placed at $$i$$-th position. The definition of $$X$$ and $$Y$$ are the same as the definition provided above.

Note that all the $$X$$ nodes has to be placed on the left and all the $$Y$$ nodes has to be placed on the right side of $$u$$ in a valid topological sort. Let's iterate through all the $$X$$ nodes; let the current one be $$v$$. We will try to merge the current topological sort with the topological sort of subtree rooted at $$v$$.

Denote $$j$$ as the position of $$v$$ in the topological sort we want to merge with. Let's fix some value $$p$$ - the position of $$u$$ after the current topological sort be merged. Now we have a inequation:

$$S_u + S_v - p - (S_u - i) \ge S_v - i + 1$$

$$i + j \ge p + 1$$

We also have $$p \ge i$$ and $$j \le S_v$$. Substituting this in the above inequation, we get:

$$i + S_v \ge i + j \ge p + 1 \ge i + 1$$

Note that $$i - 1$$ elements of the current topological sort are placed before $$p$$-th position, and $$S_u - i$$ elements of the current one are placed after $$p$$-th position. So we have the formula:

$$dp(u, p) = dp(u, i) \cdot dp(v, j) \cdot \binom{p - 1}{i - 1} \cdot \binom{S_u + S_v - p}{S_u - i}$$

Since there are no "$$j$$" in the binomial part, we use prefix sum / suffix sum to get sum of $$dp(v, j)$$ over all $$j$$ such that $$p + 1 - i \le j \le S_v$$.

The same calculation can be done for all the $$Y$$ nodes. The answer of the problem is $$\sum_{i=1}^{n} dp(1, i)$$. The total time complexity is $$O(n^2)$$.