基於內容重疊合並子列表，python 3

Question

如果我們有許多列表包含其中包含整數的子列表（對）。如果任何兩個子列表具有相同的編號，我們希望合併它們並刪除重複的數字。

例如： alist = [[2, 1], [5, 3], [5, 1], [3, 4], [3, 1], [5, 4], [4, 1], [5, 2], [4, 2]] becomes alist = [1,2,3,4,5] 而結果將是他們全部合併到一個列表，因爲他們碰巧都是共享的數字。

但並非所有的名單將是如此便捷： alist = [[4,5],[7,8],[6,7],[9,5]] 將成爲：alist = [[4,5,9],[6,7,8]] 問題是我遍歷巨大的名單，在他們10^7項。 有沒有一種方法來完成沒有兩個嵌套循環？這就是我目前所做的。

Answer 1

首先，您可以通過創建一個按數字索引的哈希表來識別哪些對共享一個成員，這些哈希表的條目是成對的集合。

您現在可以查看問題，找到連接組件（https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29）的圖形，其中節點是成對的，並且如果兩個成對的成員共享一個數字，則連接成對。正如維基百科條目所指出的那樣，您可以通過使用深度優先搜索來訪問圖中的所有節點，使用深度優先搜索來跟蹤從節點到所有其他節點的所有直接和間接鏈接相同的組件。另一種方法是使用https://en.wikipedia.org/wiki/Disjoint-set_data_structure來維護對的集合，當來自先前不同集合的兩個對共享一個數字時合併集合。