CODEWITHSUNDEEP
algorithmsorting
Avinash
Avinash

Reputation: 191

Conditional Sorting

Given N relations of the following type
eg N=4

A>B

A>C

B>C

D>A

Arrange the element of the relation in such a way that for every consecutive 'xy' in the arrangement 'x>y'

The output of the above example be DABC

Given N<20

The relations will be given in a two dimensional array

Thank you for your time.

Upvotes: 2

Views: 324

Answers (1)

amit
amit

Reputation: 178411

If there is such a solution - your problem modeled to a graph is actually a DAG.

The graph is G=(V,E) where V= { A,B,C,D} and E = { (x,y) | x < y } = { (B,A),(C,A),(C,B),(A,D) } . [You can of course extend it for bigger vertices set, based on the input].

Run a topological sort, and print the vertices in order. IFF topological sort fails - there is no solution, since the graph has cycles - so the entities don't have feasible ordering [other way around is the same reasoining].

Upvotes: 8

Related Questions