Quand utiliser

Le graphe a-t-il la même racine? → Le problème de considérer si tous ou des points spécifiques sont connectés
Le problème de considérer si plusieurs éléments sont inclus dans le même ensemble

Ce qui est bon

Très peu d'ordres de O (α (N)). α (n) est l'inverse de la fonction d'Ackermann A (n, n).

modèle

Il a créé une bibliothèque très utile. .. https://note.nkmk.me/python-union-find/ https://github.com/nkmk/python-snippets/blob/ec0e770a72135b12840ea02f1e74101785faf700/notebook/union_find.py#L1-L46

Fusionner les éléments avec ʻunion () → Obtenez le résultat souhaité avec same () ou group_count () `. Cela ne semble pas difficile

Exemple d'utilisation

ARC032 B - Construction de routes

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 même pour ces problèmes. Que i = p [i] soit remplacé ou non par ʻuf.same (i, p [i]) `.

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)

référence

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

Une expression lambda peut être utilisée comme premier argument de la fonction map. Jusqu'à présent, j'avais l'habitude de ne recevoir l'entrée que sous forme de chaîne de caractères et de la changer en int, mais il semble que cela puisse être fait collectivement en en faisant une expression lambda lorsque la valeur d'entrée est moins 1 en raison du problème d'index 0 ou d'index 1 dans la liste. ..

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