求教 Python 合并元组算法

set(itertools.chain(*arr))

没仔细看题,,,,忽略我写的吧..

不确定你程序半天没出结果的原因，但是你的 inner loop 里面不应该再从头遍历 out_list 了，因为前面的元素已经遍历过了，你把 l 里的元素换个顺序，改成[ ("e", "f"), ("a", "b"), ("b", "c")]再运行试试，肯定有重复的

union find
```
from collections import defaultdict


class DSU:
def __init__(self):
self.weights = {}
self.parents = {}

def find(self, x):
if x not in self.parents:
self.parents[x] = x
self.weights[x] = 1
return x
else:
path = [x]
while self.parents[path[-1]] != path[-1]:
path.append(self.parents[path[-1]])
root = path[-1]
for node in path:
self.parents[node] = root
return root

def union(self, elements):
roots = [self.find(e) for e in elements]
heaviest_root = max([(self.weights[root], root) for root in roots])[1]
for rot in roots:
if root != heaviest_root:
self.weights[heaviest_root] += self.weights[root]
self.parents[root] = heaviest_root


def merger(A):
"""
:type A: List[int]
:rtype: int
"""
dsu = DSU()
for a in A:
dsu.union(a)
d=defaultdict(set)
for k,x in dsu.parents.items():
d[x].add(k)
return list(d.values())
```

如果是 [("a", "b"), ("b", "c"), ("c", "d")] 呢？全合并成一个？

建立一个无向图，然后输出 里面所有没有连接在一起的子图就可以了，非常简单的。

你程序死循环的原因应该是这里
```
for item_set in out_list:
if len(temp_set & item_set) > 0:
item_set.update(temp_set)
else:
out_list.append(temp_set)
```
你不断迭代 out_list，然后又不断对它 append，就永远都遍历不完。常见错误了。

这不是并查集嘛

并查集。。。

# coding=utf-8
# input = [('a', 'b'), ('b', 'c'), ('e', 'f')]
# output = [{'a', 'b', 'c'}, {'e', 'f'}]


def union_set(items):
ret = []
mark = {}
for item in items:
for n in item:
if n in mark:
for m in item:
ret[mark[n]].add(m)
mark[m] = mark[n]
break
else:
index = len(ret)
s = set()
for n in item:
s.add(n)
mark[n] = index
ret.append(s)

return ret


if __name__ == "__main__":
inputs = [('a', 'b'), ('b', 'c'), ('a', 'e', 'f')]
print(union_set(inputs))

@aijam great，代码比较优雅

新学到两个技能：

`for-else`
`集合可用作判断，空集合可当 False`