patrickkkkk - 1 year ago 70
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.

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download