# 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?

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.