[Pour les professionnels de la concurrence] Union Find tree summary

Quand utiliser

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

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())

Recommended Posts

[Pour les professionnels de la concurrence] Union Find tree summary
[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
Résumé de la recherche Bisection pour les professionnels de la concurrence
[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage
[Pour les professionnels de la concurrence] Résumé du doublement
[Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers
[Pour les professionnels de la concurrence] Résumé de la file d'attente prioritaire (heapq)
Union Find sur networkX
Rechercher, localiser le résumé de la commande
Résumé de l'apprentissage RAPIDS