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

union find

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])

复制代码

我觉的如果你想用搜索来做的话 可以参考number of islands
我的想法是 先把他们po进无向图里，把同一个set里的先连起来，然后从A开始跑BFS找所有关联点，期间用hashset来prune去重。
不过最后列表里各个list里元素可能是无序的

Kayle_Yang 发表于 2019-8-21 01:20
我觉的如果你想用搜索来做的话 可以参考number of islands
我的想法是 先把他们po进无向图里，把同一个set ...

wow，好有趣的idea

cecilianxf 发表于 2019-8-20 20:14
Union find...
以下是一个用uf的例子
[mw_shl_code=python,true] # union find

太感谢了！网上很多template都要重新写个class，这个好棒！

标准union find，就是在看你知不知道这个数据结构，你就算用search做出来面试官也觉得不是最优解……

口才张 发表于 2019-8-21 12:49
太感谢了！网上很多template都要重新写个class，这个好棒！

这个是account merge那道题的代码（leetcode能搜到）。你把这个写一遍再把account merge那道题的主代码写一下，uf就差不多没问题了