题目内容

社交网络拓扑图中的节点表示社交网络中的用户，边表示两个用户之间的社交连接，边是无向的，两个用户最多只有一条直接相连的边。用户的影响力定义为：从某个社交网络用户开始，找出所有可以在$K$跳(直接或间接关系)内接触到的其他用户的总个数。

请实现一个程序，计算给定社交网络中某个用户在$k$跳范围内的影响力。

题面解释:

给定一个社交网络拓扑图，其中用户之间通过无向边连接。输入包含三个参数：N表示社交网络中的连接总数，M是需要计算影响力的用户编号，K是跳数范围。接下来有N行，每行两个整数，表示两个用户之间存在直接的社交连接。目标是计算用户M在K跳内能够接触到的不同用户的数量，称为该用户的影响力。输出结果为用户M在指定跳数范围内能够接触到的用户总数。

bfs

计算给定社交网络中某个用户在k跳范围内的影响力，也就是要找到所有距离m,k以内的能访问到的点，最短路问题，数据只有1e3跑一遍bfs(n^2)，之后，枚举所有点，距离小于等于k的ans+=1，最后输出ans-1(除去本身)即可

题解

该问题是典型的图论中的最短路问题，目标是在给定的社交网络中，找到某个用户$M$在$K$跳以内能够接触到的所有用户的数量。由于每条边的权值均为1，因此可以使用广度优先搜索（BFS）来计算从起始用户$M$到其他所有用户的最短路径，然后统计所有距离在$K$以内的用户数量，最终得出用户的影响力。