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 =  + 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