Disjoint Устанавливает ошибку времени пробега при сжатии пути

Question

Теперь я изучаю онлайн-курс структуры данных. Вот моя реализация Python алгоритма слияния и поиска. Я следовал инструкциям, но время работы намного превышает пределы. Может ли кто-нибудь взглянуть? Это должно быть просто. Благодарю.

Мы должны выполнять операции «m» или объединения.() и() - это номера двух таблиц с реальными данными. Если() ̸ =(), скопируйте все строки из таблицы() в таблицу(), затем очистите таблицу(), а вместо реальных данных поместите в нее символическую ссылку(). И ответ - максимальный размер таблицы строк списка. Пример порядка операций:

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

Ввод показывает, что существует 5 таблиц, и мы хотим сделать 5 операций. Каждая из таблиц имеет размер 1. Следующие пять строк показывают, что мы хотим объединить source5 в destination3, source4 к destination2 ... Вывод должен быть:

2 
2 
3 
5 
5 

Пояснение: В данном примере, все таблицы изначально имеют ровно 1 строку данных. Рассмотрим операции слияния:

1. Все данные из таблицы 5 копируется в таблице № 3. Таблица 5 теперь содержит только символическую ссылку на таблицу 3, а в таблице 3 имеет 2 строки. 2 становится новым максимальным размером.

2. 2 и 4 объединены таким же образом, как 3 и 5.

3. Мы пытаемся объединить 1 и 4, но 4 имеет символическую ссылку, указывающую на 2, так что мы на самом деле скопировать все данные из таблицы номер 2 в таблицу номер 1, очистите таблицу номер 2 и поместите в нее символическую ссылку на таблицу №1. В таблице 1 теперь три строки данных, а 3 - новый максимальный размер.

4. Перемещение по пути символических ссылок из 4 имеет 4 → 2 → 1, а путь от 5 равен 5 → 3. Таким образом, мы фактически объединяем таблицы 3 и 1. Мы копируем все строки из номера таблицы 1 в таблицу номер 3, и теперь таблица 3 имеет 5 строк данных, что является новым максимумом.

5. Все таблицы прямо или косвенно указывают на таблицу 3, поэтому все остальные слияния ничего не изменят.

Инструкция: Подумайте, как использовать непересекающиеся объединение множеств со сжатием пути и объединения по рангу эвристики, чтобы решить эту проблему. В частности, вы должны разделить в своем мышлении структуру данных, которая выполняет операции union/find из объединений таблиц. Если вас попросят объединить первую таблицу во вторую, но ранг второй таблицы меньше ранга первой таблицы, вы можете игнорировать запрошенный порядок при слиянии в структуре данных Disjoint Set Union и присоединиться к соответствующему узлу во вторую таблицу к узлу, соответствующему первой таблице, вместо этого в вас 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

Проблемы заключается в том, что вы звоните max на всех данных на каждом раунде, таким образом, имеющий O(nm) временной сложности.Вместо того, чтобы делать этот вызов 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