CODEWITHSUNDEEP
c++seqchain
P. A.
P. A.

Reputation: 53

What is the most efficient algorithm to find a longest chain from a set of ordered pairs (x, y)?

I have a set of ordered pairs (x, y) where x != y but otherwise arbitrary.
How do I find the longest chain without repeating the ordered pairs?

For example let

S = {(-1, 1.2), (4, 2), (1.2, 3), (3, 5.2), (4.2, -1), (5.2, 1), (3, 2)}.
The longest chain is formed by (-1, 1.2), (1.2, 3), (3, 5.2), (5.2, 1).
There is another chain (-1, 1.2), (1.2, 3), (3, 2) but it is not the longest.

Iterating over the entire set is one solution but it is not efficient.

Upvotes: 1

Views: 753

Answers (1)

Nayana Adassuriya
Nayana Adassuriya

Reputation: 24766

I'm not going to code.but this may help you.

You have to look about graph algorithms. Think your pair is a node with input side and output side. Then think about all the edges you can draw. then simplify the graph and use some longest path search algo uses for graphs. https://en.wikipedia.org/wiki/Longest_path_problem

Upvotes: 1

Related Questions