给定n个表示对的元组，返回带有连接的元组的列表

Question

给定n个元组，编写一个函数，该函数将返回具有连接值的列表。

例：

pairs = [(1,62),
    (1,192),
    (1,168),
    (64,449),
    (263,449),      
    (192,289),
    (128,263),
    (128,345),
    (3,10),
    (10,11)
    ]

结果：

[[1,62,192,168,289],
 [64,449,263,128,345,449],
 [3,10,11]]

我相信可以使用图或树作为数据结构，为每个值创建节点，并为每对边创建边，每个树或图代表连接的值，但是我还没有找到解决方案。

在python中产生产生这些对的连接值列表的结果的最佳方法是什么？

Answer 1

我不知道这个问题已经有了名字（感谢avim！），所以我继续天真地解决了这个问题。

该解决方案有点类似于Eli
Rose的解决方案。我决定发布它，因为对于大对的列表，它的效率更高，因为lists_by_element字典会跟踪元素所在的列表，因此我们可以避免遍历所有列表及其每个项目时间，我们需要添加一个新项目。

这是代码：

def connected_tuples(pairs):
    # for every element, we keep a reference to the list it belongs to
    lists_by_element = {}

    def make_new_list_for(x, y):
        lists_by_element[x] = lists_by_element[y] = [x, y]

    def add_element_to_list(lst, el):
        lst.append(el)
        lists_by_element[el] = lst

    def merge_lists(lst1, lst2):
        merged_list = lst1 + lst2
        for el in merged_list:
            lists_by_element[el] = merged_list

    for x, y in pairs:
        xList = lists_by_element.get(x)
        yList = lists_by_element.get(y)

        if not xList and not yList:
            make_new_list_for(x, y)

        if xList and not yList:
            add_element_to_list(xList, y)

        if yList and not xList:
            add_element_to_list(yList, x)

        if xList and yList and xList != yList:
            merge_lists(xList, yList)

    # return the unique lists present in the dictionary
    return set(tuple(l) for l in lists_by_element.values())

这是它的工作方式：http :
//ideone.com/tz9t7m