# 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 **

• If you divide by the number of friends in the largest group, you will have a group with no friends. It turns out that. *

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
}

``````