请教一个算法问题，关于合并数据的操作

[goinghugh]

有个 list 内嵌了 set, 结构如下:

[
	{1,2,3}
	{2,3}
	{3,5}
	{10,15}
]

定义: 如果一个 set 和另外的 set 有重复的元素，则表示这几个 set 是同一 group

对于输入:

[
	{1,2,3}
	{2,3}
	{3,5}
	{10,15}
]

输出应该是:

[
{1,2,3,5}
{10,15}
]

写一个合并 group 操作时遇到的这个问题，感觉和 leecode 上的 friend circle 有点像，但是他的是矩阵，我的是嵌套的结构。 求组大佬指点一二或者提醒一下类似的算法，我去借鉴一下解决思路，不用直接给我答案，谢谢~

[princelai]

如果输入是[
{1,2}
{2,3}
{3,5}
{10,15}
]

那么结果应该是[
{1,2,3}
{2,3,5}
{10,15}
]
吗

[hitmanx]

@linxiaoziruo

bitmap 如果碰到上限大就不好弄了，比如元素最大可以是 U32 甚至 U64 ；另外生成 bitmap 也需要 O(n)，n 为全部元素数量（我感觉不可能有低于 O(n)的算法，因为最坏情况下至少所有元素都需要遍历一次）

[shidenggui]

对昨天写的 union find 做了下 performance，时间复杂度约等于 O(N)，下面是结果。具体测试代码附在上面的 gist 里了。

union-find:
K rows: 100 N: 63196 time: 79 T(N)/O(N): 799
K rows: 200 N: 126404 time: 149 T(N)/O(N): 848
K rows: 400 N: 252847 time: 298 T(N)/O(N): 848
K rows: 800 N: 506194 time: 600 T(N)/O(N): 843
K rows: 1600 N: 1012045 time: 1214 T(N)/O(N): 833
K rows: 3200 N: 2024459 time: 2481 T(N)/O(N): 815

[8cbx]

感觉并查集完美解决了啊，初始化：每个元素的父是自己；然后对于每一组中的每一个元素，先判断自己是否已经有非自己的父，有则把这组的第一个元素和他的父并，否则把自己并到这组的第一个元素下面