解题思路

把用户和关注关系看成一张有向图。关系 [a,b] 表示从用户 a 可以沿一条有向边到达用户 b。

需要查询从 myId 出发，最短距离不超过 maxHop 的用户，并筛选出与 myId 至少有一个共同兴趣的用户。

处理步骤如下：

1. 先用 nodes 建立用户到兴趣集合的映射。

题目内容

在一个社交网络中，用户之间通过"关注"关系形成有向图。每个用户有两个属性：

• 用户 $ID$（整数字符串）
• 兴趣标签列表（字符串数组）

现在需要实现一个函数，查询在指定用户 $k$ 跳内（$k$ 度关系内）其他用户的兴趣和给定用户兴趣相符的用户 $ID$ 列表（不含自己）。

注意：兴趣相符是指两个用户的兴趣列表有交集。

实现函数：$queryFriends(nodes, relations, myId, maxHop)$

输入参数

1. $nodes$ - 用户节点数据
   • 类型：整数二维数组/向量
   • 每行表示一个用户，包含：[$id$, 兴趣$1$, 兴趣$2$, ...]
   • 示例：["$0$", "$music$", "$reading$"] 表示用户 $0$，有 $2$ 个兴趣：$music$ 和 $reading$
   • 所有用户 $ID$ 是 $0$ 到 $n-1$ 的连续整数对应的字符串
2. $relations$ - 关注关系
   • 类型：整数二维数组/向量
   • 每行表示一个关注关系：[关注者$ID$, 被关注者$ID$]
   • 示例：["$0$", "$1$"] 表示用户 $0$ 关注了用户 $1$
3. $myId$ - 起始用户 $ID$，示例："$0$"
4. $maxHop$ - 最大跳数 $k$，示例：$2$

返回值

• 内容：所有满足条件的用户 $ID$ 及共同的兴趣列表，如[["$0$", "$music$", "$reading$"],["$1$", "$reading$"]]

• 格式 $1$：不同用户之间按以下规则排序：

  按与起始用户的最短距离从小到大排序

  距离相同的用户，按ID对应整数值进行从小到大排序

• 格式 $2$：对于具体某用户与起始用户的共同兴趣列表按以下规则排序： 按照 $ascii$ 码序从小到大排序

• 如果没有满足条件的用户，返回空数组

约束条件

1. 用户数 $n: 1 ≤ n ≤ 10^4$，可认为用户的 $id$ 字符串对应整数范围符合该条件
2. 关注关系数 $m: 0 ≤ m ≤ 2×10^4$，若关系任一端包含不存在的点应该自动忽略，不影响原始查询诉求
3. 最大跳数 $k: 1 ≤ k ≤ 100$，大于最大跳数，按照上限 $100$ 对待
4. 每个用户最多 $10$ 个兴趣标签，可认为所有用户的兴趣个数符合该条件
5. 给定查询条件中的起始用户 $ID$ 一定存在

样例1

输入

[["0","music","sports"],["1","music","reading"],["2","music"],["3","play","music","sports"]],[["0","1"],["1","2"],["2","3"],["0","3"]],"0",2

输出

[["1","music"],["3","music","sports"],["2","music"]]

说明

从 $ID=$"$0$" 出发兴趣相同（$3$ 跳内）可以匹配到用户"$1$"、"$2$"、"$3$"，同时用户"$1$"、"$3$"跳数少，因此用户"$1$"、"$3$"在用户"$2$"之前。，又因为"$1$"相比于"$3$"整数序靠前，因此用户"$1$"在用户"$3$"。用户"$3$"中，匹配到了多项爱好，根据字母序排列，"$music$"在"$sports$"之前。

样例2

输入

[["0","music"],["1","music"],["2","music"],["3", "music"],["4","music"]],[["0","1"],["1","2"],["2","3"],["3","4"]],"0",1

输出

[["1","music"]]

说明

所有用户都满足兴趣条件，但是跳数限制在 $1$ 跳内，因此仅用户"$1$"满足条件

样例3

输入

[["0","music"]],[],"0",2

输出

[]

说明

不存在满足条件的结果，返回空数组