[GO] Minimal implementation to do Union Find in Python

Hello! I'm sorry.

Even if I sometimes have problems with Union Find, I tend to use other people's libraries, so I will write it as a review. If you think it's like a forgetful notebook for yourself

Important example AtCoder Typical Contest 001 B --Union Find https://atcoder.jp/contests/atc001/tasks/unionfind_a

It ’s a pure problem of Union Find. There is also a commentary slide, so I will understand it accordingly.

https://www.slideshare.net/chokudai/union-find-49066733 Union find (disjoint-set data structure) from AtCoder Inc

Union Find features

1. Union
2. Whether it belongs to a group (Find)

Only these two. The concrete image of group creation is like this ↓ It connects the people given by input and treats them as a tree.

Creating a group

Do you belong to a group

Whether or not they belong to a group is determined by whether or not they have the same parent.

Speeding up tip1: Path compression

If it becomes long vertically, it will take time to find a parent every time. However, this time it is important which group you belong to, so it is not so important who is connected to whom, so you can speed up by connecting directly to the parent each time you find.

Speeding up tip2: Rank

By keeping the height of the tree and connecting the lower one to the higher one, the amount of calculation of path compression is reduced and the speed is increased.

Implementation (no rank)

First, the parents of each element are managed by par (short for parents). Initially, each element does not belong to any group, so you become the parent yourself. If the number of elements is N

par = [i for i in range(N+1)]

It will be.

Next, let's say that the function that finds its parent is find, and the function that checks if the elements x and y are in the same group is same.

find

If you are a parent, return your number, and in other cases, find again to find the parent and reconnect at the same time (route compression).

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #Path compression
        return par[x]

same

We check to see if each other's parents are together to determine if they are in the same group.

def same(x,y):
    return find(x) == find(y)

unite

Check each parent and unify the parents only if they are different.

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

Summarizing the above and solving this example

N,Q = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #Path compression
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(Q):
    p,a,b = map(int,input().split())
    if p == 0:
        unite(a,b)
    else:
        if same(a,b):
            print('Yes')
        else:
            print('No')

https://atcoder.jp/contests/atc001/submissions/10365710

Pattern to implement rank

When implementing rank, it is necessary to manage the height of each vertex

N,Q = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #Path compression
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1
        
for i in range(Q):
    p,a,b = map(int,input().split())
    if p == 0:
        unite(a,b)
    else:
        if same(a,b):
            print('Yes')
        else:
            print('No')

Finally

That's the minimum implementation in Python. If you find something wrong, please let us know!

The site that I was allowed to refer to

https://atcoder.jp/contests/atc001/tasks/unionfind_a

https://www.slideshare.net/chokudai/union-find-49066733