AcWing 239. 奇偶游戏 - Python3 带边权并查集,离散化模板
原题链接
中等
作者:
vitalime
,
2022-02-20 15:55:14
,
所有人可见
,
阅读 197
n = int(input())
m = int(input())
class UF:
def __init__(self):
self.p = {}
self.d = {}
def find(self,x):
if x not in self.p:
self.p[x] = x
self.d[x] = 0
return self.p[x]
if self.p[x] != x:
parent = self.find(self.p[x])
self.d[x] ^= self.d[self.p[x]]
self.p[x] = parent
return self.p[x]
def union(self,x,y,t):
p1,p2 = self.find(x), self.find(y)
if p1 != p2:
self.p[p2] = p1
self.d[p2] = self.d[x] ^ self.d[y] ^ t
return True
else:
if (self.d[x] ^ self.d[y]) != t:
return False
else:
return True
uf = UF()
def main(m):
ans = m
for i in range(m):
x,y,op = input().split()
x,y = map(int, [x,y])
t = 0
if op == "odd":
t = 1
res = uf.union(x-1,y,t)
if not res:
return i
return ans
print(main(m))