Wann zu verwenden

Hat der Graph dieselbe Wurzel? → Das Problem zu prüfen, ob alle oder bestimmte Punkte verbunden sind
Das Problem der Überlegung, ob mehrere Elemente in demselben Satz enthalten sind

Was ist gut

Sehr wenige Ordnungen von O (α (N)). α (n) ist die Umkehrung der Ackermann-Funktion A (n, n).

Vorlage

Er hat eine sehr nützliche Bibliothek erstellt. .. https://note.nkmk.me/python-union-find/ https://github.com/nkmk/python-snippets/blob/ec0e770a72135b12840ea02f1e74101785faf700/notebook/union_find.py#L1-L46

Elemente mit union () zusammenführen → Das gewünschte Ergebnis mitsame ()odergroup_count ()erhalten. Es scheint nicht schwierig

Anwendungsbeispiel

ARC032 B - Straßenbau

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        aa, bb = map(lambda x: int(x) - 1, input().split())
        uf.union(aa, bb)
    print(uf.group_count() - 1)

ABC075 C - Bridge

def main():
    N, M = map(int, input().split())
    a, b = [], []
    for _ in range(M):
        aa, bb = map(int, input().split())
        a.append(aa - 1)
        b.append(bb - 1)
    count = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if j == i:
                continue
            uf.union(a[j], b[j])
        if uf.group_count() != 1:
            count += 1
    print(count)

ABC157 D - Friend Suggestions

def main():
    N, M, K = map(int, input().split())
    connection = [[] for _ in range(N)]
    uf = UnionFind(N)
    for i in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        connection[a].append(b)
        connection[b].append(a)
        uf.union(a, b)

    for i in range(K):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.same(c, d):
            connection[c].append(d)
            connection[d].append(c)

    ans = []
    for i in range(N):
        ans.append(uf.size(i) - len(connection[i]) - 1)
    L = [str(i) for i in ans]
    print(" ".join(L))

ARC097 D - Equals

Union Find auch für diese Probleme. Ob i = p [i] durch "uf.same (i, p [i])" ersetzt wird.

def main():
    N, M = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(lambda i: int(i) - 1, input().split())
        uf.union(x, y)

    count = 0
    for i in range(N):
        if uf.same(i , p[i]):
            count += 1
    print(count)

Referenz

https://www.slideshare.net/chokudai/union-find-49066733
https://note.nkmk.me/python-union-find/
https://github.com/nkmk/python-snippets/blob/ec0e770a72135b12840ea02f1e74101785faf700/notebook/union_find.py#L1-L46

Appendix

Ein Lambda-Ausdruck kann als erstes Argument der Kartenfunktion verwendet werden. Bisher habe ich Eingaben nur als Zeichenfolge empfangen und in int geändert, aber es scheint, dass dies gemeinsam mit einem Lambda-Ausdruck erfolgen kann, wenn der Eingabewert aufgrund des Problems 0-indiziert oder 1-indiziert in der Liste minus 1 ist. ..

map(lambda i: int(i) - 1, input().split())