某岛

… : "…アッカリ~ン . .. . " .. .
April 4, 2020

 一些 python 代码

并查集

https://en.wikipedia.org/wiki/Disjoint-set_data_structure
https://www.luogu.com.cn/problem/P3367

n, m = map(int, input().split())
p = list(range(n + 1))
r = [1] * (n + 1)

def find(x):
    if (p[x] == x):
        return x
    p[x] = find(p[x])
    return p[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if (x == y):
        return
    if (r[x] == r[y]):
        r[y] += 1
    elif (r[y] < r[x]):
        x, y = y, x
    p[x] = y

for i in range(0, m):
    cmd, x, y = map(int, input().split())
    if (cmd == 1):
        union(x, y)
    else:
        print('Y' if find(x) == find(y) else 'N')

Kruskal 最小生成树

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
https://www.luogu.com.cn/problem/P3366

def find(x):
    if (p[x] == x):
        return x
    p[x] = find(p[x])
    return p[x]
			
def union(x, y):
	# x = find(x)
	# y = find(y)
	if (x == y):
		return
	if (r[x] == r[y]):
		r[y] += 1
	elif (r[y] < r[x]):
		x, y = y, x
	p[x] = y

n, m = map(int, input().split())
p = list(range(n + 1))
r = [1] * (n + 1)

edges = []
for i in range(m):
	edges.append(list(map(int, input().split())))

edges.sort(key=lambda e:e[2]) 
mst = 0
for e in edges:
	x = find(e[0])
	y = find(e[1])
	if x != y:
		union(x, y)
		mst += e[2]
print(mst)