patrickkkkk - 9 months ago 50

Python Question

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

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
```

Source (Stackoverflow)