[Python] UnionFind ABC177D

ABC177D

Es gibt verschiedene Implementierungen von UnionFind, aber in dieser Frage ist es sehr einfach, die Implementierung zu lösen, die die Anzahl der Knoten im übergeordneten Array enthält. Die Anzahl der Knoten wird wie folgt gehalten.

-Wenn es ein Kind ist, speichert es die übergeordnete Knotennummer. Wenn es sich um eine Wurzel handelt, wird die Anzahl der Knoten als negative Zahl gespeichert. -Wenn die Zahl negativ ist, ist sie die Wurzel und ihr absoluter Wert repräsentiert die Anzahl der Knoten im Baum.

`Beispielcode`


import sys

#UnionFindTree-Klassendefinition
class UnionFind():
    #Klassenkonstruktor
    #Selbst ist die Instanz selbst
    def __init__(self, n):
        #Elternknoten-Initialisieren Sie auf 1
        self.parents = [-1] * n

    #Finde die Wurzel
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #X- und y-Bäume zusammenführen
    def union(self, x, y):
        #Auf der Suche nach Wurzeln
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#Erstellen einer Union Find-Instanz
uf = UnionFind(N)
for a, b in info:
    #Passen Sie den Index an, a,Baum beitreten b
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)