What is joint search set
In computer science, the union query set is a tree data structure, which is used to deal with the merging and query of some Disjoint Sets. A union find algorithm defines two operations for this data structure:
- Find: determines which subset the element belongs to. It can be used to determine whether two elements belong to the same subset.
- Union: merge two subsets into the same set.
Because these two operations are supported, a disjoint set is often referred to as a union find data structure or a merge find set.
And what problems can be solved by searching the set
- Grouping and pairing
- Connectivity of Graphs
- Number of sets
- Number of elements in the collection
Algorithm template
type UnionFind struct {
count int
parent []int
}
func ctor(n int) UnionFind {
uf := UnionFind{
count: n,
parent: make([]int, n),
}
for i := 0; i < n; i++ {
uf.parent[i] = i
}
return uf
}
func (uf *UnionFind) find(p int) int {
for p != uf.parent[p] {
uf.parent[p] = uf.parent[uf.parent[p]] // Path compression
p = uf.parent[p]
}
return p
}
func (uf *UnionFind) union(p, q int) {
rootP, rootQ := uf.find(p), uf.find(q)
if rootP == rootQ {
return
}
uf.parent[rootP] = rootQ
uf.count--
}
example
Topic analysis:
The problem is to find how many circles of friends there are, that is, to find the number of sets that can be solved by searching the sets.
Double traverse all students to judge whether they are friends. If they are friends, they will be added to the set. Here, you can traverse the right half of the two-dimensional matrix to reduce the number of traversals and reduce the time complexity.
Code implementation:
func findCircleNum(M [][]int) int {
n := len(M)
uf := ctor(n)
// Traverse student i, j, if M[i][j]==1 join set
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if M[i][j] == 1 {
uf.union(i, j)
}
}
}
// Then return how many sets there are
return uf.count
}
type UnionFind struct {
parents []int
count int
}
func ctor(n int) UnionFind {
uf := UnionFind{
parents: make([]int, n),
count: n,
}
for i := 0; i < n; i++ {
uf.parents[i] = i
}
return uf
}
func (uf *UnionFind) find(p int) int {
for p != uf.parents[p] {
uf.parents[p] = uf.parents[uf.parents[p]]
p = uf.parents[p]
}
return p
}
func (uf *UnionFind) union(p, q int) bool {
rootP, rootQ := uf.find(p), uf.find(q)
if rootP == rootQ {
return false
}
uf.parents[rootP] = rootQ
uf.count--
return true
}
Complexity analysis:
- Time complexity: \ (O(n^2) \). Double traversal time \ (O(n^2) \), UF Union and UF The time complexity of find is \ (O(1) \), so the total time complexity is \ (O(n^2) \).
- Space complexity: \ (O(n) \). A space of \ (O(n) \) size is required.
Topic analysis:
The problem is to find the number of islands, that is, the number of sets, which can be solved by searching sets.
The topic can be abstracted as traversing all grids (i, j). If it is land ((i, j) = '1'), merge the land on the right ((I + 1, J) = '1') and the land below ((i, j+1) == '1'); If it is water ((i, j) = '0'), merge it into a sentinel set. Finally, return the number of sets - 1.
Note: the key here is to combine the water treatment into a sentinel collection, so that the water will not exist alone, thus interfering with the judgment of the number of islands.
Code implementation:
func numIslands(grid [][]byte) int {
rows := len(grid)
if rows == 0 {
return 0
}
cols := len(grid[0])
if cols == 0 {
return 0
}
uf := ctor(rows*cols + 1)
guard := rows * cols // Sentinel: used as a collection of '0'
directions := [][]int{[]int{0, 1}, []int{1, 0}}
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
index := i*cols + j
if grid[i][j] == '1' {
for _, direction := range directions {
newI, newJ := i+direction[0], j+direction[1]
if newI < rows && newJ < cols && grid[newI][newJ] == '1' {
newIndex := newI*cols + newJ
uf.union(index, newIndex)
}
}
} else {
uf.union(guard, index)
}
}
}
return uf.count - 1
}
type UnionFind struct {
parents []int
count int
}
func ctor(n int) UnionFind {
uf := UnionFind{parents: make([]int, n), count: n}
for i := 0; i < n; i++ {
uf.parents[i] = i
}
return uf
}
func (uf *UnionFind) find(p int) int {
for p != uf.parents[p] {
uf.parents[p] = uf.parents[uf.parents[p]]
p = uf.parents[p]
}
return p
}
func (uf *UnionFind) union(p, q int) bool {
rootP, rootQ := uf.find(p), uf.find(q)
if rootP == rootQ {
return false
}
uf.parents[rootP] = rootQ
uf.count--
return true
}
Complexity analysis:
- Time complexity: \ (O(n*m) \), where N and M represent the number of rows and columns of the two-dimensional array respectively.
- Space complexity: \ (O(n*m) \). The parallel search set requires an array space of n * M size.
Topic analysis:
The problem can be understood as reserving the 'O' on the boundary and filling the others with 'X'. The 'O' on the boundary can be used as a set instead of filling this set with 'X', so it can be solved by using parallel search.
- Traverse the points on the boundary and merge 'O' into a set of sentinels.
- Traverse the points in the two-dimensional matrix and merge the right and bottom of 'O' together.
- Traverse the two-dimensional matrix and fill all that are not in the sentinel set with 'X'
Code implementation:
func solve(board [][]byte) {
n := len(board)
if n == 0 {
return
}
m := len(board[0])
if m == 0 {
return
}
uf := ctor(n*m + 1)
guard := n * m
directions := [][]int{[]int{0, 1}, []int{1, 0}}
getIndex := func(i, j int) int {
return i*m + j
}
// 1. Traverse the points on the boundary and merge 'O' into a sentinel set.
for j := 0; j < m; j++ {
if board[0][j] == 'O' {
uf.union(getIndex(0, j), guard)
}
if board[n-1][j] == 'O' {
uf.union(getIndex(n-1, j), guard)
}
}
for i := 0; i < n; i++ {
if board[i][0] == 'O' {
uf.union(getIndex(i, 0), guard)
}
if board[i][m-1] == 'O' {
uf.union(getIndex(i, m-1), guard)
}
}
// 2. Traverse the points in the two-dimensional matrix and merge the right and bottom of ` ` O ` ` ` ` together.
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 'O' {
for _, direction := range directions {
newI, newJ := i+direction[0], j+direction[1]
if newI < n && newJ < m && board[newI][newJ] == 'O' {
uf.union(getIndex(newI, newJ), getIndex(i, j))
}
}
}
}
}
// 3. Traverse the two-dimensional matrix and fill all that are not in the sentinel set with 'X'
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if !uf.isConnect(getIndex(i, j), guard) {
board[i][j] = 'X'
}
}
}
}
type UnionFind struct {
parents []int
count int
}
func ctor(n int) UnionFind {
uf := UnionFind{
parents: make([]int, n),
count: n,
}
for i := 0; i < n; i++ {
uf.parents[i] = i
}
return uf
}
func (uf *UnionFind) find(p int) int {
for p != uf.parents[p] {
uf.parents[p] = uf.parents[uf.parents[p]]
p = uf.parents[p]
}
return p
}
func (uf *UnionFind) union(p, q int) bool {
rootP, rootQ := uf.find(p), uf.find(q)
if rootP == rootQ {
return false
}
uf.parents[rootP] = rootQ
uf.count--
return true
}
func (uf *UnionFind) isConnect(p, q int) bool {
return uf.find(p) == uf.find(q)
}
Complexity analysis:
- Time complexity: \ (O(n^2) \), where N and m represent the number of rows and columns of the two-dimensional array respectively.
- Space complexity: \ (O(n^2) \). The parallel search set requires an array space of n * m size.
summary
- We should master and search the template of the set, and be able to write it quickly.
- To master and search the application scenarios of the set. For example, clustering, pairing, graph connectivity, the number of sets, the number of elements in the set, etc.
- For two-dimensional problems, turn to one-dimensional solution, such as 200 Number of islands and 130 The surrounding area.
- Finding out the "pairing" relationship between elements is the key to solve the problem. For example, a two-dimensional array, find the current position and pair it to its right and below. For example, 200 Number of islands and 130 The surrounding area.