Dies ist der erste Beitrag. Bitte weisen Sie auf Fehler hin, und ich werde versuchen, diese so weit wie möglich zu beheben.

Was ist ein Gewerkschaftsfundbaum?

Eine der Methoden zum Ausdrücken einer Menge. Eine Datenstruktur, die die Gruppierung in einer Baumstruktur ausdrückt. Der Punkt ist, dass die Zugehörigkeit zu derselben Menge zu demselben Baum gehört. wikipedia

Warum heißt es Union-Find

--Find: Findet, zu welcher Gruppe ein bestimmtes Element gehört. --Union: Füge zwei Sätze zu einem zusammen

Es heißt Union-Find, weil es diese beiden Operationen unterstützt. Aus Wikipedia

Dieses Beispiel

AtCoderBeginnerContest177-D Zusammenfassend Es gibt einige Informationen, dass A und B Freunde sind. Wenn A-B und B-C Freunde sind, ist A-C auch ein Freund. Aufgrund der obigen Ausführungen möchte ich N Personen so gruppieren, dass sie keine Freunde haben. In wie viele Gruppen müssen Sie sich aufteilen? Ist das Problem.

Strategie

Hier ist die Lösung, die ich zuerst gefunden habe. Angenommen, es gab insgesamt 9 Personen, A, B, C, D, E, F, G, H, I.

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

Wenn es so eine Freundschaft ist

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

Sie können drei Gruppen von Freunden bilden. Es ist intuitiv, dies in Gruppen ohne Freunde zu unterteilen.

A	B	C	D
E	F
G	H	I

Wenn Sie eine solche Gruppe in einer vertikalen Spalte erstellen, können Sie sehen, dass eine Gruppe ohne Freunde erstellt wird.

** Das ist **

Wenn Sie durch die Anzahl der Freunde in der größten Gruppe dividieren, haben Sie eine Gruppe ohne Freunde. Es stellt sich heraus, dass. * *

In meinem Fall ist hier jedoch ein Problem aufgetreten.

Wie kann man eine Menge darstellen?

Ich konnte nicht daran denken.

Die erste Methode, die ich mir ausgedacht habe

Ich habe mir so etwas wie eine Scheibe mit Scheiben ausgedacht, die eine Menge darstellen.

Aber es gab ein Problem damit. Überprüfen Sie, ob in allen Listen eine Person mit dem Namen A vorhanden ist, und fügen Sie dieser Gruppe in diesem Fall eine Person mit dem Namen B hinzu. Wenn es nicht enthalten ist, fügen Sie eine neue Liste hinzu und fügen Sie eine Liste hinzu, die die Gruppe dort darstellt In diesem Fall wird der Berechnungsbetrag O (N) für die Elemente der Liste bei jedem Hinzufügen maximal generiert. Da wir dies für maximal 2 * 10 ^ 5 tun müssen, beträgt der maximale Berechnungsbetrag O (1 + 2 + 3 ... 2 * 10 ^ 5), was ungefähr O (20.000, 100.000 = 2 * 10 ^ 10) entspricht. Es ist unmöglich, es mit der aktuellen Leistung des Computers in weniger als 2 Sekunden zu beenden.

Was soll ich dann tun?

Hier kommt Union Find ins Spiel.

Union Find Tree Prinzip

Angenommen, es gab insgesamt 9 Personen, 1, 2, 3, 4, 5, 6, 7, 8, 9

Mit anderen Worten, Freundschaft

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

Berücksichtigung von Teilen

Darstellung der Basisbaumstruktur

Stellen Sie sich ein Slice vor, dessen Element ein übergeordnetes Element hat.

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

Dies bedeutet, dass der Elternteil von 2 1 ist.

parent[1] == 1

Dies bedeutet, dass 1 die Wurzel ist.

NewUnionFind(num int) Union Konstruktor finden. Initialisieren Sie es so, dass Sie zuerst die Wurzel sind.

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) Funktion, die die Wurzel von x zurückgibt Übrigens aktualisiere ich das übergeordnete Element, wenn ich alle Elemente untersuche

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) Eine Funktion, die zwei Bäume zusammenführt Kann auch verwendet werden, um herauszufinden, ob es sich um dasselbe Baumelement handelt

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
}

Hauptfunktion mit den oben genannten Funktionen

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()
                //Zusammenführen der Menge, zu der a und b gehören
		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)
}

Wie der obige Code funktioniert

Wenn Sie versuchen, mit fmt.Println (unionFind) in der Mitte zu debuggen, können Sie diesen Status sehen.

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

Nachdem die gesamte Verarbeitung abgeschlossen ist, wird unionFind.Parent

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

Ist zu sein Was dies bedeutet, ist etwas überflüssig, aber zu erklären

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

index = 1 Mit anderen Worten, der Elternteil der Person Nr. 1 ist die Person Nr. 2 index = 2 Mit anderen Worten, der Elternteil der Person Nr. 2 ist die Person Nr. 3 Das Folgende repräsentiert auch alle Eltern

Übrigens aktualisiert Root () den übergeordneten Wert mit dem Root-Wert, um den Rechenaufwand beim Zählen zu verringern. Es gibt jedoch noch einige Auslassungen. Wenn Sie also zählen, wird die Root-Funktion verwendet, um erneut nach dem übergeordneten Element zu suchen, wie unten gezeigt.

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

Zusammenfassung

Mit dem obigen Algorithmus konnten wir diese Frage mit der Union Find-Methode beantworten. Ich würde es begrüßen, wenn Sie einen Kommentar abgeben könnten, wenn Sie auf etwas hinweisen, das schwer zu verstehen oder falsch ist, oder wenn Sie der Meinung sind, dass dies klüger ist.

Zum Schluss möchte ich noch die vollständige Quelle posten.

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
}

Implementieren und verstehen Sie den Union-Find-Baum in Go