0

我现在正在学习在线数据结构课程。这是我的合并和查找算法的 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 现在有 3 行数据，3 成为新的最大大小。

  4. 从4遍历符号链接的路径我们有4→2→1，而从5的路径是5→3。所以我们实际上是合并表3和1。我们将表号1的所有行复制到表号中3，现在3号表有5行数据，是新的最大值。

  5. 现在所有表都直接或间接指向表 3，因此所有其他合并不会改变任何内容。

说明：思考如何使用带路径压缩的不相交集并集和秩启发式并集来解决这个问题。特别是，您应该将执行联合/查找操作的数据结构与表的合并区分开来。如果要求将第一个表合并到第二个，但是第二个表的rank小于第一个表的rank，在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)
4

1 回答 1

0

问题是您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
于 2016-08-31T07:06:40.777 回答