Implement and understand union-find trees in Go

This is the first post. Please point out any mistakes, and I will try to fix them as much as possible.

What is a union-find tree?

――One of the methods to express a set. A data structure that expresses grouping in a tree structure. The point is that belonging to the same set belongs to the same tree. wikipedia

Why it is called union-find

--Find: Finds which set a particular element belongs to. --Union: Merge two sets into one

It is called Union-Find because it supports these two operations. From wikipedia

This example

AtCoderBeginnerContest177-D In summary There is some information that A and B are friends. If A-B and B-C are friends, then A-C is also a friend. Based on the above, I would like to group N people so that they have no friends. How many groups do you need to divide into? It is a problem.

Tactics

Here is the solution I first came up with. Assuming there were a total of 9 people, A, B, C, D, E, F, G, H, I

A B
B C
D B
E F
G H
H I

If it ’s a friendship like that

A-B-C-D
E-F
G-H-I

You can make three groups of friends. Intuitively dividing this into groups with no friends

A B C D
E F
G H I

If you make a group like this in a vertical column, you can see that a group with no friends is created.

** That is **

However, in my case, a problem occurred here.

How to express a set?

I couldn't think of it.

The first method I came up with

I came up with something like a slice with slices that represent a set.

But there was a problem with this. Check if the list includes a person named A, and if so, add a person named B to that group. If it is not included, add a new list and add a list representing the group there If this is done, the amount of calculation O (N) for the elements of the list will be generated at the maximum each time it is added. Since we have to do it for a maximum of 2 * 10 ^ 5, the calculation amount is a maximum of O (1 + 2 + 3 ... 2 * 10 ^ 5), which is about O (20,000,100,000 = 2 * 10 ^ 10). It is impossible to finish in less than 2 seconds with the current computer power.

Then what should I do?

This is where Union Find comes in.

Union Find Tree Principle

Assuming there were a total of 9 people, 1, 2, 3, 4, 5, 6, 7, 8, 9

1 2
2 3
4 2
5 6
7 8
8 9

In other words, friendship

1-2-3-4
5-6
7-8-9

Consideration of parts

Representation of the base tree structure

Consider a slice whose element has a parent.

N=9
parent := make([]int, N)
parent[2]=1

This means that the parent of 2 is 1.

parent[1] == 1

This means that 1 is the root.

NewUnionFind(num int) A constructor of Union Find. Initialize it so that you are the root at first.

type UnionFind struct {
	Parent []int
}

func NewUnionFind(num int) UnionFind {
	parent := make([]int, num+1)
	for i := 0; i < len(parent); i++ {
		parent[i] = i
	}
	return UnionFind{parent}
}

Root(x int) A function that returns the root of x By the way, I'm updating the parent when exploring all the elements

func (uf *UnionFind) Root(x int) int {
	if uf.Parent[x] == x {
		return x
	}
	uf.Parent[x] = uf.Root(uf.Parent[x])
	return uf.Parent[x]
}

Unite(x, y int) A function that merges two trees Can also be used to find out if they are the same tree element

func (uf *UnionFind) Unite(x, y int) bool {
	xRoot := uf.Root(x)
	yRoot := uf.Root(y)
	if xRoot == yRoot {
		return false
	}
	uf.Parent[xRoot] = yRoot
	return true
}

Main function using the above functions

func main() {
	scn := NewScanner()
	n, m := scn.Geti(), scn.Geti()
	if m == 0 {
		fmt.Println(1)
		return
	}
	unionFind := NewUnionFind(n)
	for i := 0; i < m; i++ {
		a, b := scn.Geti(), scn.Geti()
                //You are merging the set to which a and b belong
		unionFind.Unite(a, b)
	}

	ar := make([]int, n+1)
	for _, in := range unionFind.Parent {
		ar[unionFind.Root(in)]++
	}
	ans := 0
	for _, in := range ar {
		ans = Max(ans, in)
	}
	fmt.Println(ans)
}

How the above code works

If you debug with fmt.Println (unionFind) in the middle, you can see this state.

9 6
1 2
2 3
4 2
5 6
7 8
8 9
{[0 2 3 3 3 6 6 8 9 9]}
4

After all the processing is done, unionFind.Parent

[0 2 3 3 3 6 6 8 9 9]

Is to be What this means is a bit verbose, but to explain

index 0 1 2 3 4 5 6 7 8 9
parent 0 2 3 3 3 6 6 8 9 9

index = 1 In other words, the parent of No1 person is No2 person index = 2 In other words, the parent of No2 person is No3 person Similarly, all of them represent parents.

By the way, in order to reduce the amount of calculation when counting, Root () updates the parent value with the root value. However, it still causes omissions, so when counting, the Root function is used to search for the parent again as shown below.

ar := make([]int, n+1)
for _, in := range unionFind.Parent {
	ar[unionFind.Root(in)]++
}

Summary

With the above algorithm, we were able to answer this question using the union Find method. I would appreciate it if you could comment if you point out something that is difficult to understand or wrong, or if you have an opinion that this is smarter.

Finally I would like to post the full source.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scn := NewScanner()
	n, m := scn.Geti(), scn.Geti()
	if m == 0 {
		fmt.Println(1)
		return
	}
	unionFind := NewUnionFind(n)
	for i := 0; i < m; i++ {
		a, b := scn.Geti(), scn.Geti()
		unionFind.Unite(a, b)
	}

	ar := make([]int, n+1)
	for _, in := range unionFind.Parent {
		ar[unionFind.Root(in)]++
	}
	ans := 0
	for _, in := range ar {
		ans = Max(ans, in)
	}
	fmt.Println(ans)
}

func Max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

type UnionFind struct {
	Parent []int
}

func NewUnionFind(num int) UnionFind {
	parent := make([]int, num+1)
	for i := 0; i < len(parent); i++ {
		parent[i] = i
	}
	return UnionFind{parent}
}

func (uf *UnionFind) Root(x int) int {
	if uf.Parent[x] == x {
		return x
	}
	uf.Parent[x] = uf.Root(uf.Parent[x])
	return uf.Parent[x]
}

func (uf *UnionFind) Unite(x, y int) bool {
	xRoot := uf.Root(x)
	yRoot := uf.Root(y)
	if xRoot == yRoot {
		return false
	}
	uf.Parent[xRoot] = yRoot
	return true
}

// Scanner is a base structure
type Scanner struct {
	bufScanner *bufio.Scanner
}

// New inits a scanner
func NewScanner() *Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(nil, 100000000)
	return &Scanner{scanner}
}

// Geti scans number from stdin
func (scanner *Scanner) Geti() int {
	sc := scanner.bufScanner
	sc.Scan()
	str := sc.Text()

	num, err := strconv.Atoi(str)
	if err != nil {
		panic(err)
	}
	return num
}

Recommended Posts

Implement and understand union-find trees in Go
Implement recursive closures in Go
Implement UnionFind (equivalent) in 10 lines
Neural network to understand and implement in high school mathematics
Understand Cog and Extension in discord.py
[Required subject DI] Implement and understand the mechanism of DI with Go
Implement FIR filters in Python and C
Understand and implement ridge regression (L2 regularization)
Java programmer touched Go language (Implement Java inheritance in Go language)
Implemented memoization recursion and exploration in Python and Go
Y / n processing in bash, python and Go
Carefully understand the exponential distribution and draw in Python
Plot and understand the multivariate normal distribution in Python
Easy HTTP server and Systemd autostart settings in Go
Carefully understand the Poisson distribution and draw in Python
Artificial intelligence, machine learning, deep learning to implement and understand
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Go language to see and remember Part 7 C language in GO language
Implement Enigma in python
Write Pulumi in Go
Implement recommendations in Python
Implement XENO in python
Understand in 10 minutes Selenium
Implement sum in Python
Implement Traceroute in Python 3
I wrote it in Go to understand the SOLID principle