python有3个样例RE为什么，刚学python求大佬解惑

titank @ 2021-05-14 21:53:12

def init(n):
    for i in range(1,n+1):
        fa[i]=i
def find(n):
    if n == fa[n] :
        return n
    return find(fa[n])
def uni(x,y):
    fa[find(x)] = find(y)
n,m = map(int, input().split())
fa = [0]*(n+1)
init(n)
for i in range(0,m):
    z,x,y = map(int, input().split())
    if z == 1:
        uni(x,y)
    if z == 2:
        if find(x) == find(y):
            print('Y')
        else:
            print('N')

by metaphysis @ 2021-05-15 07:19:10

@titank

使用并查集的路径压缩，测试数据有可能给出的是一条链，导致递归深度过深。

def init(n):
    for i in range(1,n+1):
        fa[i]=i
def find(n):
    if n == fa[n] :
        return n
    fa[n] = find(fa[n]);
    return fa[n]
def uni(x,y):
    fa[find(x)] = find(y)
n,m = map(int, input().split())
fa = [0]*(n+1)
init(n)
for i in range(0,m):
    z,x,y = map(int, input().split())
    if z == 1:
        uni(x,y)
    if z == 2:
        if find(x) == find(y):
            print('Y')
        else:
            print('N')

by titank @ 2021-05-15 10:44:59

@metaphysis 我把查询操作改为循环为甚么会超时啊。。。

by metaphysis @ 2021-05-15 11:13:06

@titank

要做路径压缩，不然测试数据退化成一条链，每次查询的时间复杂度将是 O(n)，无法发挥并查集的优势。建议您百度一下并查集的路径压缩技巧。

by titank @ 2021-05-16 09:28:16

@metaphysis 哦，懂了。感谢(^_^)