分辨多个用户之间是否是分身的算法？

[Grocker]

我有一个需求是为了分辨多个用户之间是否是分身（需求背景是为了防止新注册用户薅羊毛，优惠力度挺大的，是分身的用户只要一人享受了优惠，其他人不能再次享受）， 所以我要将多个用户之间人为的去关联，比如用户 A 关联了 B ，A 和 B 互为分身；用户 B 再关联了 C ，B 和 C 互为 分身，C 和 A 也互为分身，因为有中间人 B ，以此类推，中间人的层级不限，这种用推荐使用什么算法实现呢？

我自己想到的是多存数据将这种层级平铺：

当用户 A 直接关联用户 B 时，我们在 associations 表中插入两条记录：

associations 表结构：user_id 关联用户 ID ，associated_user_id：被关联用户 ID ，is_direct：是否是直接关联

INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (A 的用户 ID, B 的用户 ID, TRUE);
INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (B 的用户 ID, A 的用户 ID, TRUE);

当用户 B 再直接关联用户 C 时，不仅插入 B 和 C 之间的直接关联记录，还插入 A 和 C 之间的间接关联记录：

INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (B 的用户 ID, C 的用户 ID, TRUE);
INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (C 的用户 ID, B 的用户 ID, TRUE);
INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (A 的用户 ID, C 的用户 ID, FALSE);
INSERT INTO associations (user_id, associated_user_id, is_direct) VALUES (C 的用户 ID, A 的用户 ID, FALSE);

需要用到的场景有： 取消关联某两个用户之间的关联 查询给定用户的所有分身

[GBdG6clg2Jy17ua5]

算法应该是并查集。
数据库设置上，我觉得可以设置为（ user_id,root_associated_user_id,associated_user_id ）
查看两个用户是否是关联。直接看他们是不是同一个 root_associated_user_id 即可。root_associated_user_id 是真身，associated_user_id 是直接关联人（这个备用，方便以后将关系人传成链条）

[GBdG6clg2Jy17ua5]

还得补充下，这里有个路径压缩问题，原有 A->B ,C->D 关联，后面来了个 B->C ，可以考虑遍历到最顶，也可以考虑在添加关系的时候进行路径压缩，更新 root_associated_user_id 。个人建议不需要压缩，直接遍历查询就行了。因为关系链不会很长。

[tangtang369]

https://leetcode.cn/problems/accounts-merge/description/ 看看这一题

[Grocker]

@angryfish （ user_id,root_associated_user_id,associated_user_id ）以 A->B 的话，这三个字段分别是？

[showB1]

imei 设备 id 呗

[4S3wVwsEaEc3ktu8]

如果愿意搞一个专门的系统做这个事，感觉就是 16 楼说的图数据库。问题就是一个连通图问题。跟社交软件的好友关联差不多。

[R4rvZ6agNVWr56V0]

你这个方法没用，这需要很系统化的风控策略，不止是用户信息层面

[txzhanghuan]

你这需要建设一套营销风控体系了。

[importmeta]

既然优惠力度很大，接入金融级人脸识别 SDK ，价格一块钱一次。。。

[SSang]

没有算法能实现你这种需求

[SSang]

我建议，你先把需求分析清楚了再提问，你都都线下辨别了，你干嘛不让业务人员自己去查表？

[realrojeralone]

不讨论业务场景，只从技术层面看，图数据库能满足需求吗？

[Grocker]

@realrojeralone 图数据库可以满足，只是走的有点远，并查集也能满足，以及 12 楼的也能满足

[longlonglanguage]

1.看网络，一般一家人回家都连 Wifi
2.看 sim 卡，可能存在一种场景，当前手机内并未装“相应的 sim 卡”，然而却输入的相应的 sim 卡号码
3.看账号的登录设备，一般情况下小孩会有一个设备专门用来“学习”
4.还可以在 123 条检测后，只要重复，就直接把对应的手机号记录进黑名单
5.不建议执行 1234 条，更不建议执行第 4 条，因为这会让你的顾客极度的不爽。

[GBdG6clg2Jy17ua5]

@Grocker "（ user_id,root_associated_user_id,associated_user_id ）以 A->B 的话，这三个字段分别是？"

就像并查集一样，这里是要有初始化值的。为了让这个集合不太大，就放购买课程的人员吧。不用放全部用户进行初始化。
首先：用户 A 购买课程，表里就一条记录(A,A,NULL)
然后：B 购买就加条记录(B,A,A).
如果后面 C 购买，关系是 B->C 的，就增加一条记录（ C,A,B ）

若果出现 D->E,（ D,D,NULL ）,（ E,D,D ）
再出现一个 C->D 的话，这里可以自己衡量一下，如果查找很频繁，用户间关系很多的话，就进行路径压缩，否则直接查找就行了
最终，这个表的大小就是购买用户的数量。

[Pteromyini]

从数据结构说感觉可以构建最小生成树之类的，试试并查集？

[Pteromyini]

@Pteromyini #56 像是在找联通子图

[timpaikex]

楼主实际上要的是每个上课的娃只能用一次优
惠啊
那实际上应该对上课的娃的身份上做文章，保证每一个上课的娃都只有一个账号呗？说白了就是给上课娃的做实名制保证唯一，问题不就解决了？
至于可能出现的冒充身份上课问题，上传照片啥的可解，但是不建议做太多限制，有羊毛薅家长才会觉得不买亏

[zyxcompany]

有网络指纹 还是排除不了硬件更换

[lchynn]

用房产证吧， 一本产证只能一个号。