不相交集路径压缩运行时间误差

Question

我正在选修一门在线数据结构课程。这里是我的Python实现的合并和查找算法。我遵守了指示，但运行时间远远超过了限制。有人能看看吗？应该是简单的。谢谢。

我们必须进行合并或工会活动。()和()是具有实际数据的两个表的编号。如果()̸= ()，将所有行从table ()复制到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. 表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，因此所有其他合并都不会更改任何内容。

说明:考虑如何使用不相交集合并和路径压缩，并通过秩启发式方法来解决这个问题。特别是，您应该在思考中将执行联合/查找操作的数据结构与表的合并分开。如果要求将第一个表合并为第二个表，但第二个表的秩小于第一个表的秩，则可以在不相交集Union数据结构中合并时忽略请求的顺序，并将对应于第二个表的节点加入到与第一个表对应的节点中，而不是在不相交的集合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