Construct a DAG from given multiple topological orderings
Approach 1
For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3.
According to your approach, we will get a cycle 1-&gt;2-&gt;3-&gt;4-&gt;1. We then remove 3-&gt;4 and 4-&gt;1, and obtain a graph:
     ______
    /      \
1-&gt;2-&gt;4-&gt;5-&gt;3
 \______/

Now 5-&gt;3 and 1-&gt;2 respectively violate the first and the second orders, so we remove them, and get
     ______
    /      \
1  2-&gt;4-&gt;5  3
 \______/

Now node 2 has 2 outgoing edges. Removing either one makes a final graph where 3 nodes (1, 2, 3 or 1, 2, 4) have in-degree 0.
However, there exists a graph
1-&gt;3 2-&gt;4-&gt;5

where both orders are satisfied but only 2 nodes have in-degree 0.
So Approach 1 is incorrect.
Approach 2
Consider an optimal solution. Every edge in this optimal solution must be the form $(a_i,a_j)$ where $i&lt;j$ in each order. This means all edges in the optimal solution are contained in the intermediate graph. So if you then remove the outgoing edges such that the number of nodes having in-degree 0 is minimum, you will get a correct optimal solution.
However, your approach that trying to make the number of nodes having in-degree 0 minimum is incorrect.
For example, consider the three orders:
\begin{align}
1, 2, 3, 4, 5, 6, 7, 8 \\
5, 1, 6, 3, 8, 2, 4, 7 \\
2, 7, 3, 8, 1, 4, 5, 6
\end{align}
First we can obtain the following intermediate graph:
    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3-&gt;4 5-&gt;6 7 8
 \ \__/
  \__/

Applying your approach, we will remove 1-&gt;4, 2-&gt;4 and 3-&gt;4 (or 3-&gt;8), and there are 5 nodes with in-degree 0: 1, 2, 3, 4 (or 8), 5. However, the optimal solution would be
     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5-&gt;6 7 8
 \___/

where only 4 nodes have in-degree 0: 1, 2, 3, 5.