Disjoint 设置路径压缩运行时间错误

Question

我现在正在上在线数据结构课程。这是我的 Python 合并和查找算法的实现。我按照说明进行操作，但运行时间远远超过了限制。谁能看一下？它应该是一个简单的。谢谢

我们必须进行 'm' 合并或联合操作。 () 和 () 是两个 table 具有真实数据的数字。如果 () ̸=()，复制从 table () 到 table () 的所有行，然后清除 table () 并代替实际数据放入符号 link 把 () 放进去。答案是列表行的最大 table 大小。操作顺序示例：

输入显示有5个table，我们要进行5次操作。每个 table 的大小为 1。以下五行显示我们要将 source5 合并到 destination3，将 source4 合并到 destination2 ... 输出应该是：

说明：在这个示例中，所有 table 最初只有 1 行数据。考虑合并操作：

所有来自 table 5 的数据都被复制到 table 数字 3。Table 5 现在只包含符号 link 到 table 3，而 table 3 有 2 行。 2 成为新的最大尺寸。
2和4的合并方式与3和5相同。
我们试图合并1和4，但是4有一个符号link指向2，所以我们实际上把table这个数字2的所有数据复制到table 数字 1，清除 table 数字 2 并将符号 link 放入其中的 table 数字 1。 Table1现在有3行数据，3成为新的最大尺寸。
从4遍历符号links的路径我们有4→2→1，从5开始的路径是5→3。所以我们实际上是合并tables 3和1。我们将table号1的所有行复制到table号3中，现在table号3有5行数据，这是新的最大值.
所有 table 现在直接或间接指向 table 3，所以所有其他合并都不会改变任何东西。

说明：思考如何使用带路径压缩的不相交集并集和按等级启发式并集来解决这个问题。特别是，您应该在思考中将执行 union/find 操作的数据结构与 table 的合并分开。如果您被要求将第一个 table 合并到第二个，但第二个 table 的等级小于第一个 table 的等级，您可以在合并时忽略请求的顺序在 Disjoint Set Union 数据结构中，将对应于第二个 table 的节点连接到对应于第一个 table 的节点，而不是在您的 Disjoint Set Union 中。但是，您需要存储实际第二个 table 的编号，您被要求将第一个 table 合并到相应的不相交集的父节点中，并且您需要一个额外的字段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，而是存储结果并在每次合并后更新它，以防目标 table 大于当前最大值。使用路径压缩，这将导致 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

Disjoint 设置路径压缩运行时间错误

Disjoint Sets path compression running time error

python

data-structures

disjoint-sets

Disjoint 设置路径压缩运行 时间错误

Disjoint Sets path compression running time error

python

data-structures

disjoint-sets

Disjoint 设置路径压缩运行时间错误