• 题目地址
• 思路
• 代码
  • • MySQL代码
    • 等效Cypher查询(未验证)

题目地址

https://leetcode.cn/problems/strong-friendship/

思路

就是在无向图中寻找这个pattern：

(* Mathematica *)
GraphData[{"CompleteTripartite", {1, 1, 3}}]

SQL写还是比较麻烦。
更加复杂的查询还是建议把数据迁移到neo4j这样的图数据库，然后写Cypher这样的图数据库查询语句。

代码

MySQL代码

with t1 as( -- 图中找到的所有   v1-e1-v2-e2-v3 pattern
    select * from(
        select f1.user2_id as uid , f1.user1_id as one_degree_connected , f2.user1_id as two_degree_connected
        from Friendship f1 
        join Friendship f2 
        on f1.user1_id=f2.user2_id
        union 
        select f1.user2_id as uid , f1.user1_id as one_degree_connected , f2.user2_id as two_degree_connected
        from Friendship f1 
        join Friendship f2 
        on f1.user1_id=f2.user1_id
        union
        select f1.user1_id as uid , f1.user2_id as one_degree_connected , f2.user1_id as two_degree_connected
        from Friendship f1 
        join Friendship f2 
        on f1.user2_id=f2.user2_id
        union 
        select f1.user1_id as uid , f1.user2_id as one_degree_connected , f2.user2_id as two_degree_connected
        from Friendship f1 
        join Friendship f2 
        on f1.user2_id=f2.user1_id
    )tmp1
    where uid<>two_degree_connected and uid<>one_degree_connected and one_degree_connected<>two_degree_connected
    and uid<two_degree_connected
)

select uid as user1_id, two_degree_connected as user2_id
, count(distinct one_degree_connected) as common_friend
from t1

where concat(uid,",",two_degree_connected) in (select concat(user1_id,",",user2_id) from Friendship) -- 坚定的友谊要求这两人还得是朋友

group by user1_id,user2_id
having common_friend>=3
order by user1_id,user2_id,common_friend

等效Cypher查询(未验证)

MATCH (u1)-[:FRIENDSHIP]-(common_friend)-[:FRIENDSHIP]-(u2),
      (u1)-[:FRIENDSHIP]-(u2)
WHERE NOT (u1)-[:FRIENDSHIP]-(u2)-[:FRIENDSHIP]-(common_friend)
WITH u1, u2, COLLECT(DISTINCT common_friend) AS common_friends
WHERE SIZE(common_friends) >= 3
RETURN u1 AS user1_id, u2 AS user2_id, SIZE(common_friends) AS common_friend_count
ORDER BY user1_id, user2_id, common_friend_count