patrickkkkk patrickkkkk - 1 year ago 57
Python Question

Disjoint Sets path compression running time error

I am taking an online data structure course now. Here is my Python implementation of a merge and find algorithm. I followed the instructions, but the running time far exceeds the limits. Can anyone take a look? It should be a simple one. Thanks.

We must do 'm' merges or union operations.

Answer Source

The problem is that you're calling max on the whole data on each round thus having O(nm) time complexity. Instead of doing that call the max on initial data, store the result and after each merge update it in case destination table is larger than current max. With path compression this will result to O(max(m, n)) time complexity.

n, m = map(int, raw_input().split())
rank = [0] + map(int, raw_input().split())
parent = range(n + 1)
current_max = max(rank)

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

for source, dest in (map(int, raw_input().split()) for _ in xrange(m)):
    source, dest = find_parent(source), find_parent(dest)
    if source != dest:
        if rank[source] > rank[dest]:
            source, dest = dest, source
        parent[source] = dest
        rank[dest] += rank[source]

    current_max = max(current_max, rank[dest])  
    print current_max