[For competition professionals] Union Find Tree Summary

When to use

What is good

Very few orders of O (α (N)). α (n) is the reciprocal of the Ackermann function A (n, n).

template

He has created a very useful library. .. https://note.nkmk.me/python-union-find/ https://github.com/nkmk/python-snippets/blob/ec0e770a72135b12840ea02f1e74101785faf700/notebook/union_find.py#L1-L46

Merge elements with ʻunion ()→ Get the desired result withsame ()orgroup_count ()`. It doesn't seem difficult

Example of use

ARC032 B --Road construction

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 even for these problems. Whether or not i = p [i] is replaced with ʻ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)

reference

Appendix

You can use a lambda expression as the first argument of the map function. Until now, I used to only receive input as a character string and change it to int, but it seems that it can be done collectively by making it a lambda expression when the input value is minus 1 due to the problem of 0-indexed or 1-indexed in the list. ..

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

Recommended Posts

[For competition professionals] Union Find Tree Summary
[For competition professionals] Minimum spanning tree summary
Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Summary of doubling
[For competition professionals] Prime number, divisor, prime factorization summary
[For competition pros] Priority queue (heapq) Summary
Union Find on networkX
Find, locate command summary
Summary for learning RAPIDS