辗转不纪年 @ 2020-09-18 22:56:08
class Union_find_set(object):
def __init__(self, n):
self.__fa = list(range(n))
self.__size = [1] * n
def __findfa(self, x):
if x == self.__fa[x]:
return x
else:
self.__fa[x] = self.__findfa(self.__fa[x])
return self.__fa[x]
def find_father(self, x):
return self.__findfa(x)
def same_set(self, x, y):
return self.__findfa(x) == self.__findfa(y)
def union_set(self, x, y):
fx, fy = self.__findfa(x), self.__findfa(y)
if fx == fy:
return None
if self.__size[fx] < self.__size[fy]:
self.__fa[fx] = fy
self.__size[fy] += self.__size[fx]
else:
self.__fa[fy] = fx
self.__size[fx] += self.__size[fy]
n, m = [int(x) for x in input().split(' ') if x.isdigit()]
ufs = Union_find_set(n)
for t in range(m):
z, x, y = [int(x) for x in input().split(' ') if x.isdigit()]
x, y = x - 1, y - 1
if z == 1:
ufs.union_set(x, y)
elif ufs.same_set(x, y):
print('Y')
else:
print('N')
最近学了Python,本想用这个并查集写一个类来练练手,但是交上去全是RE,下载了测试数据,在本地是可以正常运行的,想问问大佬这是什么情况?
by zhanghengrui @ 2020-09-18 23:38:43
@辗转不纪年 输入用这种:
a, b, c = map(int, input().split())
洛谷数据换行符可能是 CRLF,然后 split(' ')
的话最后一个会带一个 \r
,.isdigit()
返回 False
,所以会少一个元素,直接 RE
by 辗转不纪年 @ 2020-09-19 15:59:05
@zhanghengrui 解决了,太感谢了!!Orz