[Competitive Pro Struggle] Implemented Union Find

motivation

I'm a weak programmer, but I decided to start competitive programming in order to become a strong programmer. As you can see when you try it, you often remember it. I think that even if you are solving math in the exam, thinking ability is of course important, but in order to reach the answer in a short time in the actual exam, it is also important to have a lot of drawers.

Therefore, we will implement the main algorithms and data structures one by one.

This time, which is the first time, we will implement a data structure called Union Find.

By the way, since the motivation for competing pros is to do business efficiently, I will use my favorite language Python instead of C ++, which is used by all competing pros rather than Po ** Hub. (I saw in some article that C ++ is 4 times faster, but 4 times is an error, isn't it?)

UnionFind UnionFind is when N nodes are divided into several groups

1. Connect the groups to which any two nodes a and b belong into one group.
2. Determine if any two nodes a and b belong to the same group A data structure specialized for this function.

Both can be implemented with the leveling complexity log (N).

algorithm

All images are from Nice slides

Implementation

data structure

Weak programmers don't know how to hold data first, but UnionFind is a tree structure that ** remembers who the parent node is. So if you want to group n nodes, you just need a ** list that holds the parents of each node **.

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))
    ...

By the way, since the root node has no parent, ** the parent expresses it as its own node = root node. ** ** At first, they are all root nodes because they are initialized as separate groups.

Judgment

    def is_united(self, x, y):
        return self._root(x) == self._root(y)

As you can see in the image quoted from the nice slide, you just have to determine if the root nodes are the same, so use the _root method to pull the root nodes and compare if they are equal. That's fine.

When writing code, I think that it is easiest to write the entire algorithm quickly by thinking that there is already a completed function for the detailed sub-algorithm.

If you didn't cook for 3 minutes and said, "I have smoked potatoes here today," you wouldn't be able to see the whole picture of the dish.

Join

    def union(self, x, y):
        self.parents[self._root(y)] = self._root(x)

This is also exactly what was written on the nice slide, and if you want to combine x's group and y's group, you can just attach one of the root nodes to the other's root node.

Even if you say to attach, you just specify the parent of the node you want to attach to the node to attach to.

Get the root node

The only sub-algorithm I've used so far is _root, so implementing this should be complete.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            return root

In order to return the root node, it is only necessary to recurs back to the parent node until a node whose parent becomes itself appears. The UnionFind tree data structure is easy because it refers to the parent of each node.

However, it was written on a great slide that the amount of calculation would be lighter if the Tree structure was as flat as possible due to the amount of calculation.

So I'll add some ingenuity to the code.

    def _root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root = self._root(self.parents[x])
            self.parents[x] = root  #Reconnect directly to the parent node.
            return root

This completes Union Find!

Try to move

uf = UnionFind(5)
uf.union(0, 3)
uf.union(1, 3)
print(uf.is_united(0, 1))  # True

The end

I'm looking for a companion who will work hard as an engineer together. I would be very happy if you follow LGTM, Follow, and Twitter.