This is the first post. Please point out any mistakes, and I will try to fix them as much as possible.
――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
--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
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.
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.
I couldn't think of it.
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.
This is where Union Find comes in.
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
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
}
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)
}
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)]++
}
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