Несвязанный Устанавливает ошибку времени сжатия пути

Question

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

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

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 строки данных, и 3 становится новым максимальным размером.

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

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

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