不相交設置路徑壓縮運行時間錯誤

Question

我正在參加在線數據結構課程。這是我的Python合併和查找算法的實現。我按照說明操作，但運行時間遠遠超出了限制。任何人都可以看看嗎？它應該是一個簡單的。謝謝。

我們必須做'合併'或合併操作。 （）和（）是具有實際數據的兩個表的數量。如果（）̸=（），將table（）中的所有行復制到table（）中，然後清除表（），而不是真正的數據將符號鏈接放入（）中。答案是列表行的最大表格大小。操作順序示例：

5 5 
1 1 1 1 1 
3 5 
2 4 
1 4 
5 4 
5 3 

輸入顯示有5個表，我們要執行5個操作。每個表的大小爲1，接下來的5行顯示，我們要合併到source5 destination3，source4到DESTINATION2 ... 輸出應該是：

2 
2 
3 
5 
5 

說明：在此示例中，所有表最初有一行數據。考慮合併操作：

1. 所有從表5的數據複製到表號。表5，現在只包含一個符號鏈接表3，表3有2行。 2成爲新的最大尺寸。

2. 2和4相同的方式被合併爲3和5

3. 我們正試圖合併1和4，但4具有指向2符號鏈接，所以我們實際上覆制所有數據從表號2到表號1，清除表號2，並在其中放置表號爲1的符號鏈接。表1現在有3行數據，3成爲新的最大大小。

4. 從4中遍歷符號鏈接的路徑，我們有4→2→1，而從5開始的路徑是5→3。所以我們實際上是合併了表3和1.我們複製表中的所有行1放入表號3中，現在表號3具有5行數據，這是新的最大值。

5. 所有的表現在直接或間接地指向表3，因此所有其他合併都不會改變任何內容。

指令： 想想如何使用路徑壓縮和聯盟的分離集工會按職級啓發式來解決這個問題。特別是，你應該在思維中分離出執行聯合/查找操作的數據結構。如果要求您將第一個表合併到第二個表中，但第二個表的等級小於第一個表的等級，則可以在合併不相交集數據結構時忽略請求的順序，並加入相應的節點到第二個表到第一個表對應的節點，而不是在你的Disjoint Set Union中。但是，您需要存儲要求將第一個表合併到相應Disjoint Set的父節點中的實際第二個表的編號，並且您需要在Disjoint Set Union的節點中存儲一個附加字段來存儲它。

這裏是我的代碼中使用秩啓發和路徑壓縮來實現它：

# python2 
import sys 

n, m = map(int, sys.stdin.readline().split()) 
lines = list(map(int, sys.stdin.readline().split())) 
rank = [1] * n 
rank_original=[1]*n 
parent = list(range(0, n)) 
ans = max(lines) 

rank=lines 

for i in range(len(lines)): 
    rank[i]=lines[i] 
    rank_original[i]=lines[i] 


def getParent(i): 
    # find parent and compress path 
    if i!=parent[i]: 
     parent[i]=getParent(parent[i]) 
    return parent[i] 

def merge(destination, source): 
    realDestination, realSource = getParent(destination), getParent(source) 

    if realDestination == realSource: 
     return False 
    if rank[realDestination]>=rank[realSource]: 
     parent[realSource]=realDestination 
     rank[realDestination] += rank[realSource] 

     rank_original[realDestination]=rank[realDestination] 

    else: 
     parent[realDestination]=realSource 
     rank[realSource]+=rank[realDestination] 
     rank_original[realDestination]=rank[realSource] 

    rank_original[source]=0 

    return True 

for i in range(m): 
    destination, source = map(int, sys.stdin.readline().split()) 
    merge(destination - 1, source - 1) 
    ans=max(rank) 
    print(ans) 

Answer 1

的問題是，你對因此具有O(nm)時間複雜度每輪整個數據調用max。而不是在初始數據上調用max，而不是在初始數據上調用max，而是保存結果並在每次合併後更新它，以防目標表大於當前最大值。使用路徑壓縮時，這將導致時間複雜度爲O(m + n)。

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