题目描述
算法1
并查集
参考文献
视频讲解
Python 代码
n, k = map(int, input().split())
p = [i for i in range(n + 1)] # 每个节点的父节点,初始都是自己
d = [0 for i in range(n + 1)] # 每个节点到根节点的额距离,初始都是到自己是0
# 规定一下,到根节点距离余3
# 为0,和根节点同一类
# 为1,吃根节点
# 为2,被根节点吃
def find(x): # 超重x的根节点,并更新x和路径上各个节点到根节点的距离
if p[x] != x:
# 这样不对
# 想一下父节点就是根节点的情况
# 这样d[x]会变为原来的2被
# 正确的应该就是将p[x]备份一下
# t_px = d[p[x]] # x的父节点到根节点的距离
# p[x] = find(p[x]) # 将x的父节点指向p[x]的根节点
# d[x] += t_px # x到根节点的距离加上x原父节点到根节点的距离
t = p[x]
p[x] = find(p[x])
d[x] += d[t]
return p[x]
res = 0
for _ in range(k):
op, x, y = map(int, input().split())
if x > n or y > n:
res += 1
else:
px, py = find(x), find(y)
if op == 1: # x,y同一类
if px == py: # 有同一个根节点,在同一个集合中
if d[x] % 3 != d[y] % 3: # 但不是同一类,假的
res += 1
else: # 不在一个集合中,将px和py合并
p[px] = py # 将x的根节点的父节点指向y的根节点
# 计算px到py之间的距离
# 新的dx要和dy同余
# (dx + dxy - dy) % 3 = 0
dxy = d[y] - d[x]
while dxy < 0: # 保证一下他是正的
dxy += 3
d[px] = dxy
else: # x吃y
if x == y:
res += 1
else:
if px == py:
if (d[x] - d[y]) % 3 != 1:
res += 1
else: # 不是同一个根节点,合并,让x吃y
p[px] = py # 将x的根节点的父节点指向y的根节点
# 计算px到py之间的距离
# 新的dx-1要和dy同余(x更远一点)
# (dx - 1 + dxy - dy) % 3 = 0
dxy = d[y] - d[x] + 1
while dxy < 0: # 保证一下他是正的
dxy += 3
d[px] = dxy
print(res)