There are many questions about and check set, the official data is 30 (by 2020-02-20), but there are some questions although the official did not paste and check set label, but the use and check set is very simple. This kind of questions if you master the template, then brush this kind of questions will be very fast, and the probability of making mistakes will be greatly reduced, this is the benefit of the template.

Here I summarize a few topics and check the set:

  • 547. A circle of friends
  • 721. Account consolidation
  • 990. Satisfiability of equality equations

You can learn the template to apply the above three problems, do not come out can see my solution.

And look up the set overview

And the search set algorithm mainly solves the problem of “dynamic connectivity” in graph theory

The union-find algorithm solves the problem of dynamic connectivity of graphs. This algorithm itself is not difficult. Whether it can be applied mainly depends on your ability to abstract the problem, whether you can abstract the original problem into a graph theory problem.

If you are not familiar with this algorithm, I recommend reading this article about the union-find algorithm in great detail.

You can think of the elements of a parallel set as people in a department, and how many people make up a department number.

And the three methods of searching the core of the set are union, find and Connected.

  • union: Merge two departments of two people into one department (if two people are in the same department, there is no need to merge)

(Photo by Labuladong)

  • find: Finds someone’s department leader
  • connnected: Judge whether two people belong to the same department

(Photo by Labuladong)

The template

This is a template THAT I use a lot, and I make small changes depending on the topic, but it’s basically the same.

Class UF: parent = {} CNT = 0 def __init__(self, M): # def find(self, x): while x! = self.parent[x]: x = self.parent[x] return x def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] = self.find(q) self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q)Copy the code

If you want better performance, this template is for you, and the code is slightly more complex.

Class UF: parent = {} size = {} CNT = 0 def __init__(self, M): # def find(self, x): while x! = self. Parent [x]: x = self. Parent [x] = self. return x def union(self, p, q): if self.connected(p, q): Return # The small tree hangs on the big tree, Leader_p = self.find(p) leader_q = self.find(q) if self.size[leader_p] < self.size[leader_q]: self.parent[leader_p] = leader_q else: self.parent[leader_q] = leader_p self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q)Copy the code

You can use different templates depending on your situation.