# Sort sequence from topological sort if another value is being important

We have sequence that we got from topological sort, but because the graph may not be connected in all cases, we should sort this sequence with another factor.

We should output permutation of numbers from $1$ to $n$ such that we also have graph $G$ that is without cycle and might be not connected and array $A$ of integers that is keeping another information for each nod. Now for each pair $(i,j)$ node $j$ should be after node $i$ if they are connected, meaning node $j$ is under node $i$, on other hand if not $j$ is not under $i$, they are not connected, they should be compared with the another array A and sorted with that array.

So, if node $j$ is not reachable from node $i$, node $j$ should be after $i$ if $A_j$ is greater than $A_i$

For example, let our graph have 3 nodes and 1 edge: $(1, 2)$. If $B$ after the topological sort is $\{ 3, 1, 2\}$ and another sequence $A_1 = 5, A_2=8, A_3=1$. We should sort the sequence $B=\{1, 2, 3\}$. We cannot put $2$ before $1$ because we will break the topological sort rule give above.

I was thinking about using normal sorts, but they are not giving correct results.

Your requirements may not be simultaneously satisfiable. Consider the graph with three nodes $1,2,3$, and a single edge $1 \to 2$. Suppose the array $A$ is $[15,5,10]$. Then node 1 is not reachable from node 3 and $A_1 > A_3$, so your requirement says node 1 should be after node 3. Also node 3 is not reachable from node 2 and $A_3 > A_2$, so your requirement says that node 3 should be after node 2. Finally based on the graph, we require node 1 to be before node 2. These three requirements are not simultaneously satisfiable.
• The sort actually should be in the reverse order, node $j$ should be after node $i$ if $A_j > A_i$, so the output permutation is 1 3 2. We want to keep the topological order, but if more answers are possible we want to compare them on $A$, smallest first (but keep the topological order) – someone12321 Mar 9 '18 at 17:13
• The topology is most important, and after we have done this topology sort over the graph, if more than one answer is possible. For our case (1, 2, 3), (1, 3, 2), (3, 1, 2) are all valid topologically sorted sequences over our graph, but we want to reorder now such that the smallest from $A$ is first etc.., so in first position can go 1 and 3, because A[3] is smaller 3 will go first, and now the permutation must be 3 1 2 – someone12321 Mar 10 '18 at 8:49
• Also please note that the sequence may not be sorted always correctly by $A$. – someone12321 Mar 10 '18 at 8:51