Union Find (+deadly mistake)

as mentioned in https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-4368%EB%B2%88-%EB%B3%84%EC%9E%90%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0

Then, we do the typical find_parent and union BUT i keep making this deadly mistake in union. Omg for union i keep making the same mistaking of making parent of node2 as parent 1. It should be parent of parent2 should be parent1, not node2. Lets logically think this through. Union means we are trying to combine 2 sets together. We combine via assigning parents together, not the nodes!

v impt

also union find isnt for directed graphs!. For those, it is topo sort.

wrong:

def union(node1, node2):
    par1 = find_parent(node1)
    par2 = find_parent(node2)
    if par1 < par2:
        parent[node2] = par1
    else:
        parent[node1] = par2

correct:

def union(node1, node2):
    par1 = find_parent(node1)
    par2 = find_parent(node2)
    if par1 < par2:
        parent[par2] = par1
    else:
        parent[par1] = par2

union find lazy loads! not eagerly loads

What I mean is just doing union on all given edges doesnt necessarily give the deepest parent!

for example
n=6 edges=[[0,1],[2,3],[4,5],[1,2],[3,4]] parent = [0, 0, 0, 0, 0, 4]. Here the last node's parent should also be 0 but its not eagerly loaded.

So u MUST call find_parent at the end, not just get parent[node]

time

union find follows inverse Ackermann function, which is very slow-growing, so even for large n, the function remains almost a constant so it is o(1)