# Algorithm to match / link complementary pairs

I'm working on a problem where I have a large number of pairs

e.g

1 -> 2

4 -> 3

2 -> 8

..

And a "match" would be considered 1 -> 2 and 2 -> 8 to make 1 -> 2 -> 8, as "1 -> 2" ends with 2 and "2 -> 8" starts with 2.

Given a large set of pairs, i'd like to create the longest possible chain. I know I could brute force it, but I'm wondering if there is a better way

Edit - I can give more precise context for the problem (Sorry, i'm a student currently in data structures who has not taken an algorithms course)

The datapoints in the pairs would be song names which well flow together. There is a subreddit called "/r/ocrableach" which posts pairs of songs where the ending of one song blends well with the beginning of another song.

An item can appear multiple times in the data set, but i will be discarding repeats as i build my chain.

I'd like to pull posts from /r/ocrableach and try to build the longest continuous playlist based on the song pairs.

If I have the pairs

"Okra -> Bleach"
"Bleach -> I THINK"
"On God" -> "Okra"


I'd like to start constructing a linked list like this:

"Okra -> Bleach" and "Bleach -> "I THINK" match
= "Okra -> Bleach -> I THINK"

"Okra -> Bleach -> I THINK" and "On God -> Okra" match
= "On God -> Okra -> Bleach -> I THINK"


I'm essentially checking if the tail of one pair matches with the head of the "chain" to see if it can be added.

• Can an item appear multiple times? for examples 1-->2, 2-->8, 2-->32 ? – Yamar69 Nov 29 '19 at 10:19
• Can you edit the question to give a precise definition of the problem? What's the definition of a chain? An example is not a substitute for a general problem specification. Are you asking for the longest simple path in a directed graph? the longest walk? Something else? What's the context where you encountered the problem? – D.W. Nov 29 '19 at 19:48
• @D.W. I've updated the post so hopefully, it should be more clear – nrobins1 Nov 29 '19 at 21:02

Assuming you don't want to repeat a song, this is the problem of finding a longest path in a directed graph. Here the graph has one vertex per song, and an edge $$s \to t$$ if the ending of song $$s$$ blends well with the beginning of song $$t$$.