题目标题

实现一个并查集,并查集中的数据只考虑ASCII编码中的字符。

参考解析
  1. 有时限并查集的代码,但是只考虑ASCII编码中的字符是什么意思?
  2. 实现一个并查集的代码(参考:https://www.cnblogs.com/yscl/p/10185293.html):
  3. class UnionFind(object):
  4. 2 """并查集类"""
  5. 3 def __init__(self, n):
  6. 4 """长度为n的并查集"""
  7. 5 self.uf = [-1 for i in range(n + 1)] # 列表0位置空出
  8. 6 self.sets_count = n # 判断并查集里共有几个集合, 初始化默认互相独立
  9. 7
  10. 8 # def find(self, p):
  11. 9 # """查找p的根结点(祖先)"""
  12. 10 # r = p # 初始p
  13. 11 # while self.uf[p] > 0:
  14. 12 # p = self.uf[p]
  15. 13 # while r != p: # 路径压缩, 把搜索下来的结点祖先全指向根结点
  16. 14 # self.uf[r], r = p, self.uf[r]
  17. 15 # return p
  18. 16
  19. 17 # def find(self, p):
  20. 18 # while self.uf[p] >= 0:
  21. 19 # p = self.uf[p]
  22. 20 # return p
  23. 21
  24. 22 def find(self, p):
  25. 23 """尾递归"""
  26. 24 if self.uf[p] < 0:
  27. 25 return p
  28. 26 self.uf[p] = self.find(self.uf[p])
  29. 27 return self.uf[p]
  30. 28
  31. 29 def union(self, p, q):
  32. 30 """连通p,q 让q指向p"""
  33. 31 proot = self.find(p)
  34. 32 qroot = self.find(q)
  35. 33 if proot == qroot:
  36. 34 return
  37. 35 elif self.uf[proot] > self.uf[qroot]: # 负数比较, 左边规模更小
  38. 36 self.uf[qroot] += self.uf[proot]
  39. 37 self.uf[proot] = qroot
  40. 38 else:
  41. 39 self.uf[proot] += self.uf[qroot] # 规模相加
  42. 40 self.uf[qroot] = proot
  43. 41 self.sets_count -= 1 # 连通后集合总数减一
  44. 42
  45. 43 def is_connected(self, p, q):
  46. 44 """判断pq是否已经连通"""
  47. 45 return self.find(p) == self.find(q) # 即判断两个结点是否是属于同一个祖先