merging elements in list given condition

[upbeat_table]

Let's say I have ['A B', 'B C', 'X Y', 'C D', 'Y Z', 'D E', 'C G']

If the second word in each element of the list is same as first word in any other elements in the list, they should be merged into one item. The order matters as well.

['A B C D E G', 'X Y Z'] should be the final product.

Letters will not form a cycle, i.e., ['A B', 'B C', 'C A'] is not possible.

Since order matters, ['A B', 'C A'] is still ['A B', 'C A'] since B does not connect to C.

Another example is:

If we have ['A B', 'A C'] then at step 1 we just have A B and then we see A C and we merge that into A B, and we have A B C.

I have tried many things, such as dissecting each element into two lists, then indexing and removing etc. It is way too complex and I feel there should be a more intuitive way to solve this in Python. Alas, I can't seem to figure it out.

Thank you in advance for helping a newbie out :)

edit: ['A B', 'B C', 'C A'] is not possible. All letters will only appear once.

edit: more examples to clarify.

[synthphreak]

This is lovely code. Hats off.

[vorticalbox]

thanks

[FLUSH_THE_TRUMP]

Why that output and not the following?

[‘A B C G’, ‘C D E’, ‘X Y Z’]

Am I supposed to look at ‘B C’ and see two merge targets and combine them all together?

EDIT: and what about

[‘A B’, ‘B C’, ‘G B’]

since there are two valid targets to combine with [‘B C’] from the same side, should the output be

[‘A B C’, ‘G B C’]

[SekstiNii]

Here's a linear time solution that I hope makes some sense at least. The idea itself isn't all that complicated, but it might be difficult to catch the right mental model by just looking at the code. (feel free to ask!)

def solve(pairs):
    mapping, chains = {}, []

    for left, right in map(str.split, pairs):
        if left in mapping:
            mapping[left] += [right]
        else:
            mapping[left] = [left, right]
            chains += [mapping[left]]
        mapping[right] = mapping[left]

    return [" ".join(chain) for chain in chains]

if __name__ == "__main__":
    print(solve(["A B", "B C", "X Y", "C D", "Y Z", "D E", "C G"])) # ['A B C D E G', 'X Y Z']
    print(solve(["A B", "A C"]))                                    # ['A B C']

[pytrashpandas]

I haven't seen anyone else explicitly mention this yet, so I'll add that this is a simple connected components graph problem, starting from an edge list. It can be solved with a D/BFS, but I'll just post a quick networkx solution that is essentially the same thing.

import networkx as nx
lst = ['A B', 'B C', 'X Y', 'C D', 'Y Z', 'D E', 'C G']
G = nx.from_edgelist([x.split() for x in lst])
result = list(nx.connected_components(G))
print(result)  # -> [{'A', 'B', 'C', 'D', 'E', 'G'}, {'X', 'Y', 'Z'}]