python-网络分析

解题思路:

并查集(秩+路径压缩)

用python运行依然超时，70分。

注意事项：

参考代码：

def find(x):  
    global fa  
  
    if x == fa[x]:  
        return x  
    else:  
        fa[x] = find(fa[x])  
        return fa[x]  
  
def merge(i,j):  
    global fa,rank  
  
    x = find(i)  
    y = find(j)  
    if rank[i] <= rank[j]:  
        fa[x] = y  
    else:  
        fa[y] = x  
  
    if rank[x] == rank[y] and x!= y:  
        rank[y] = rank[y]+1  
  
def f(n,m):  
      
    Rst = [0 for i in range(n+1)]  
    for i in range(m):  
        a,b,c = map(int,input().strip().split())  
        if a == 1:  
            merge(b,c)  
        elif a == 2:  
            for i in range(1,n+1):  
                if find(i) == find(b):  
                    Rst[i] = Rst[i]+c  
                      
    for i in range(1,n+1):  
        print(Rst[i],end=' ')  
      
      
if __name__ == '__main__':  
    n,m = map(int,input().strip().split())  
    fa = [i for i in range(n+1)]  
    rank = [1 for i in range(n+1)]  
    f(n,m)