前两天面试的一道题，想不出来应该用什么方法！求大神解答！

题目很简单：求联通区域，输入是[[A, B, C], [B, D], [E]]，就表明ABC联通，BD联通，E是单独的，这样可以得到ABCD联通，所以就返回：[[A, B, C, D], [E]]

感觉在leetcode上没有遇到相似的题目， 我刷题也不太多大概200道左右，不知道应该用BFS还是DFS，也不知道具体应该怎么写？
希望地里面的大神有看见的可以解答一下！反正面试挂了，但是还是很想知道应该怎么做哈哈哈。




补充内容 (2019-8-15 12:20):
如果有朋友可以帮忙加个米就更好了

补充内容 (2019-8-15 12:20):
. Waral dи,这个题是字节跳动美研所的电面的题，面试官冷冷的完全不说话也不给提示。。。

典型的Union Find题目，楼主可以在Leetcode上找找相应的tag做一下

感觉有点像leetcode里的merge interval

Union find...
以下是一个用uf的例子

1. # union find
   
2.     def initialize(self,accounts):
   
3.         self.id_to_email = {}
   
4.         self.father = {}
   
5.         for user_id, emails in enumerate(accounts):
   
6.             self.father[user_id] = user_id
   
7.             self.id_to_email[user_id] = set(emails[1:])
   
8.     def find(self,user_id):
   
9.         path = []
   
10.         while user_id != self.father[user_id]:
    
11.             path.append(user_id)
    
12.             user_id = self.father[user_id]
    
13.         for n in path:
    
14.             self.father[n] = user_id
    
15.         return user_id
    
16.             
    
17.     def union(self,d1, d2):
    . Χ
18.         root_id1 = self.find(d1)
    
19.         root_id2 = self.find(d2)
    
20.         if root_id1!= root_id2:
    
21.             self.father[root_id1] = root_id2
    
22.             self.id_to_email[root_id2] = self.id_to_email[root_id1].union(self.id_to_email[root_id2])

复制代码

waoxc 发表于 2019-8-15 12:07
. check 1point3acres for more.典型的Union Find题目，楼主可以在Leetcode上找找相应的tag做一下

嗯嗯朋友们都说是union find, 我在想可以可以用搜索实现

TGGSJ911 发表于 2019-8-15 12:16
感觉有点像leetcode里的merge interval

这个input中每个list不是只有两个元素啊，可以有好几个并且无序，感觉和merge interval差别挺大的呀

口才张 发表于 2019-8-15 12:18
嗯嗯朋友们都说是union find, 我在想可以可以用搜索实现

可以，build一个无向graph，以你的例子，{a--b--c, b--d, e}, "--"代表一条边，然后用一个visited set做DFS，比较麻烦，还是推荐union find

口才张 发表于 2019-8-15 12:19
这个input中每个list不是只有两个元素啊，可以有好几个并且无序，感觉和merge interval差别挺大的呀

感觉还是可以每个数组排序，字典序这种，然后用merge interval的方法。

最直接的就是按照开头排序（比如放到堆），然后根据 a[1] > b[0] 判断是否是重合的

leetcode 标准 UnionFind，先Union ➕path compression ~ O(n)，第二遍扫UF结构，找出根节点相同的子区域就好。第一遍遍历的时候可以加个map，省掉第二遍的遍历搜索。

的确是 union-find. 楼上几位已经给出了答案。