百度面试题：集合合并
stone54321277
题目
给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}，将其中交集
不为空的集合合并，要求合并完成后的集合之间无交集。例如上例应输出{aaa bbb ccc ddd hhh}, {eee fff},
{ggg}
要求
请描述你解决这个问题的思路
请给出主要的处理流程，算法，以及算法的复杂度
请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）
可以用并查集，扫描一遍就可以了，改进：路径压缩、按大小合并
3个月前 by cadence
0
(1)设字符窜集合个数是n,申请一个整形数组set大小是n,set[0,1,...n-1]初始化未自身的索引值，即set[0]=0,set
[1]=1,set[2]...即每个集合指向自己。同时构建一个空的可以比较字符窜(根据ASCII值)的AVL树-avltree
(2)
for 字符窜集合i in 所有字符窜集合{
for 字符窜str in 集合i{
如果str可以插入avltree里说明前面的集合中没有str字符窜，设置当前插入str的节点值是i，表明这个str属于字符窜集合i
否则插入不成功，str已经在avltree里，假如它的节点值是j，说明集合i和集合j有公共字符窜str,由于集合合并的原因,j可能不是包含它的
母集合的根，要找到母集合根，要顺着s=set[j],t=set[s]...找，直到某个t=set[t]循环，我们需要把集合j与集合t合并，方法
是让set[t]=i，即把前面出现的集合都合并到以集合i作为根的集合上来，这样就不用担心前面多个与i相交集合之间的合并问题，为了减少寻找的次
数，可以采用路径压缩的方法。
}
}
(3)最后输出的时候，先扫描set[]看看有多少个不相交集合，找到这些集合的母集合根，构成rootset，查找不相交集合的时候可以进一步用路径
压缩的方法。
for root in rootset{
遍历avltree的每个节点，因为当前节点的节点值是原始集合的根，可以通过set数组判断它是否属于root为根的集合，若是则输出。
}
时间复杂度分析，前两个for是有关字符窜的插入操作和集合查找操作。设所有字符窜数量为m，avltree插入操作的时间复杂度总共是O
(mlogm)，集合查找在平均状态下O(m*alpha),alpha可以看成一个常数，所以第二步的时间是O(mlogm)。第三步主要工作是遍历
avltree树k次，k是最后集合的数量，每次遍历时间是O(m)，总共要O(mk).
通过以上分析可知该算法的时间复杂度是O(mlogm+m*k)，如果要优化，可以考虑寻找这样的方法，即输出时如何有效找到属于一个集合字符窜的方
法。