Python 怎么实现归并集合功能？

[zealinux]

比如

输入：[(A, B), (B, C), (X,Y)]
输出：[(A, B, C), (X, Y)]

即归并有相同元素的集合。

有没有现成的库？

或者自己实现的化思路是什么样的？

[niknik]

楼下帮我回一下，我上个厕所👇

[shyrock]

这不是元组列表吗。。。哪里有集合。。。

[bumz]

并查集？

[bumz]

@shyrock #2 逻辑上的集合

[ybbswc]

首先判断是否有相同元素，有的话就作并集。楼下来吧。(ーー;)

[bumz]

亲测并查集可行，复杂度 O(n)，n 为输入中唯一元素的个数 * 每种元素平均出现次数

https://gist.github.com/bumfo/26fc4865e27b48385ed650cd08fe6004

[bumz]

@bumz #6 想要 set 的话把 tuple 改成 set 一样

[bumz]

@bumz #6 复杂度 O(n log m)，m 是不同元素的个数，n 是 m * 每个元素的平均出现次数

[bumz]

@ybbswc #5 这种做法复杂度 O(ab), a 是集合的个数，b 是每个集合中元素的个数的平均值

[freemoon]

```
a = [(1,2), (2,3)]
b = [(1,2)]

print(set(a) | set(b))
```

[strict]

复杂度目前想到的全是 m*n

[xor]

@strict 并查集可以 n log m

[xor]

@xor 并查集可以做到在现实中 O(m)
严格来讲 O(m α(n)) 但是现实中 α(n) <= 4