这里的 Hash 做法是指每个点随机一个权值,将所有点的出度 outoutout 与权值 valvalval 相乘并求和,判断是否为 ∑val\sum val∑val,即判断:
非常粗略地算了一下,如果有一些 valvalval 加起来是 000 就可能挂,或者一些 valvalval 的和与另一些 valvalval 的和相等就可能挂。
这样相当于 2105+31052^{10^5}+3^{10^5}2105+3105 个数中有一个是 000 就会挂?
这样的正确率貌似不太高?