题目描述
将同一连通图的点存与数组,且该数组可以利用根节点序号查找
样例
n,m = map(int,input().split())
p = [0] + [i for i in range(1,n+1)]
d = [[i] for i in range(0,n+1)]
cnt = [0] + [0 for i in range(1,n+1)]
def find(x):
t = x
while x!=p[x]:
x = p[x]
while t!=x:
j = p[t]
p[t] = x
t = j
return x
def merge(a,b):
if find(a)!=find(b):
d[find(b)] += d[find(a)]
p[find(a)] = find(b)
def message(p,t):
for i in d[find(p)]:
cnt[i] += t
for i in range(0,m):
s,a,b = map(int,input().split())
if s == 1:
merge(a,b)
if s == 2:
message(a,b)
print(‘ ‘.join([str(x) for x in cnt[1:]]))
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla