When to use

Does the graph have the same root? → The problem of considering whether all or specific points are connected
The problem of considering whether multiple elements are included in the same set

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

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

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