Ceci est le premier message. Veuillez signaler toute erreur et j'essaierai de les corriger autant que possible.
--Une des méthodes pour exprimer un ensemble. Une structure de données qui exprime le regroupement dans une structure arborescente. Le fait est qu'appartenir au même ensemble appartient au même arbre. wikipedia
--Find: recherche à quel ensemble appartient un élément particulier. --Union: fusion de deux ensembles en un
Il s'appelle Union-Find car il prend en charge ces deux opérations. De wikipedia
AtCoderBeginnerContest177-D En résumé Selon certaines informations, A et B sont amis. Si A-B et B-C sont amis, alors A-C est aussi un ami. Sur la base de ce qui précède, je voudrais regrouper N personnes afin qu'elles n'aient pas d'amis. Dans combien de groupes devez-vous vous diviser? C'est le problème.
Voici la solution que j'ai trouvée en premier. En supposant qu'il y avait un total de 9 personnes, A, B, C, D, E, F, G, H, I
A B
B C
D B
E F
G H
H I
Si c'est une amitié comme ça
A-B-C-D
E-F
G-H-I
Vous pouvez vous faire trois groupes d'amis. Il est intuitif de le diviser en groupes sans amis.
| A | B | C | D |
|---|---|---|---|
| E | F | ||
| G | H | I |
Si vous créez un groupe comme celui-ci dans une colonne verticale, vous pouvez voir qu'un groupe sans amis est créé.
** C'est **
Cependant, dans mon cas, un problème est survenu ici.
Je ne pouvais pas y penser.
Je suis venu avec quelque chose comme une tranche avec des tranches qui représentent un ensemble.
Mais il y avait un problème avec cela. Vérifiez si la liste comprend une personne nommée A et, le cas échéant, ajoutez une personne nommée B à ce groupe. S'il n'est pas inclus, ajoutez une nouvelle liste et ajoutez-y une liste représentant le groupe Si cela est fait, le montant de calcul O (N) pour les éléments de la liste sera généré au maximum à chaque fois qu'il est ajouté. Comme nous devons le faire pour un maximum de 2 * 10 ^ 5, le montant maximum du calcul est O (1 + 2 + 3 ... 2 * 10 ^ 5), ce qui équivaut à environ O (20,000,100,000 = 2 * 10 ^ 10). Il est impossible de le terminer en moins de 2 secondes avec la puissance actuelle de l'ordinateur.
C'est là qu'intervient Union Find.
En supposant qu'il y avait un total de 9 personnes, 1, 2, 3, 4, 5, 6, 7, 8, 9
1 2
2 3
4 2
5 6
7 8
8 9
En d'autres termes, l'amitié
1-2-3-4
5-6
7-8-9
Considérez une tranche dont l'élément a un parent.
N=9
parent := make([]int, N)
parent[2]=1
Cela signifie que le parent de 2 est 1.
parent[1] == 1
Cela signifie que 1 est la racine.
NewUnionFind(num int) Constructeur Union Find. Initialisez-le pour que vous soyez le root au début.
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) Fonction qui renvoie la racine de x Au fait, je mets à jour le parent en explorant tous les éléments
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) Une fonction qui fusionne deux arbres Peut également être utilisé pour savoir s'il s'agit du même élément d'arbre
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()
//Fusion de l'ensemble auquel appartiennent a et b
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)
}
Si vous essayez de déboguer avec fmt.Println (unionFind) au milieu, vous pouvez voir cet état.
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
Une fois que tout le traitement est terminé, unionFind.Parent
[0 2 3 3 3 6 6 8 9 9]
Est d'être Ce que cela signifie est un peu redondant, mais pour expliquer
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| parent | 0 | 2 | 3 | 3 | 3 | 6 | 6 | 8 | 9 | 9 |
index = 1 En d'autres termes, le parent de la personne No1 est No2 person index = 2 En d'autres termes, le parent de la personne No2 est No3 person Les suivants représentent également tous les parents
À propos, afin de réduire la quantité de calcul lors du comptage, Root () met à jour la valeur parent avec la valeur racine. Cependant, cela échoue toujours, donc lors du comptage, la fonction Racine est utilisée pour rechercher à nouveau le parent comme indiqué ci-dessous.
ar := make([]int, n+1)
for _, in := range unionFind.Parent {
ar[unionFind.Root(in)]++
}
Avec l'algorithme ci-dessus, nous avons pu répondre à cette question en utilisant la méthode union Find. Je vous serais reconnaissant si vous pouviez commenter si vous signalez quelque chose qui est difficile à comprendre ou qui est faux, ou si vous pensez que c'est plus intelligent.
Enfin, je voudrais publier la source complète.
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