leetcode-cheat/src/codeTemplates/uf.js at 0.1 · leetcode-pp/leetcode-cheat · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import ufLogo from "../imgs/uf.svg";

export default {
  title: "并查集",
  logo: ufLogo,
  list: [
    {
      text: "不带权并查集",
      problems: [
        {
          title: "547. 朋友圈",
          id: "friend-circles",
        },
        {
          title: "721. 账户合并",
          id: "accounts-merge",
        },
        {
          title: "990. 等式方程的可满足性",
          id: "satisfiability-of-equality-equations",
        },
        {
          title: "1202. 交换字符串中的元素",
          id: "smallest-string-with-swaps",
        },
      ],
      codes: [
        {
          language: "py",
          text: `
class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)
        `,
        },
      ],
    },
    {
      text: "带权并查集",
      problems: [
        {
          title: "399. 除法求值",
          id: "evaluate-division",
        },
      ],
      codes: [
        {
          language: "py",
          text: `
class UF:
  def __init__(self, M):
      # 初始化 parent，weight
      self.parent = {}
      self.weight = {}
      for i in range(M):
          self.parent[i] = i
          self.weight[i] = 0

  def find(self, x):
      if self.parent[x] != x:
          ancestor, w = self.find(self.parent[x])
          self.parent[x] = ancestor
          self.weight[x] += w
      return self.parent[x], self.weight[x]
  def union(self, p, q, dist):
      if self.connected(p, q): return
      leader_p, w_p = self.find(p)
      leader_q, w_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.weight[leader_p] = dist + w_q - w_p
  def connected(self, p, q):
      return self.find(p)[0] == self.find(q)[0]
        `,
        },
      ],
    },
  ],
  link:
    "https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md",
};