大家好，我是吴师兄。
校招圈有流传一句话:
几年前你对迪子爱理不理，现在你高攀不起
。
我是万万没想到，如今的迪子已经高攀到由于接收的简历太多，导致 HR 为了更加轻松的招聘，采取先只看简历这种一刀切的方式来快速筛选优质候选人，这样哪怕后续发现招聘的人有问题，也可以直接用学历搪塞出去。
或许也是不得已的一种做法，毕竟之前听说过，迪子校招 24 小时收到过 12 万份简历，如果按照以往的逻辑和规格进行筛选，那不知道猴年马月才能筛选完毕。
看每年迪子的员工数量在逐年递增，就知道有多少人愿意去投递简历。
|
时间
|
2020
|
2021
|
2022
|
2023
|
截止2024年9月
|
|
员工数量
|
22万
|
28.82万
|
57万
|
70.35万
|
90万
|
...
回归我们公众号的主题。
继续来一道和「大厂秋招」相关的算法原题。
题目描述
社交网络拓扑图中的节点表示社交网络中的用户，边表示两个用户之间的社交连接，边是无向的，两个用户最多只有一条直接相连的边。
用户的影响力定义为：从某个社交网络用户开始，找出所有可以在
k
跳（直接或间接关系）内接触到的其他用户的总个数。
请实现一个程序，计算给定社交网络中某个用户在
k
跳范围内的影响力。
输入描述
-
第一行输入
N M K
(三个空格分隔的正整数)：
N
代表社交网络连接总数，
M
代表需要计算影响力的用户编号，
K
代表计算影响力的范围。
1<=N,K<=1000
，
0<=M<1000
-
接下来的
N
行，每行两个整数
X Y(0<=X,Y<=1000)
，代表社交网络中一条直接连接的边，如
1 2
代表
1
号与
2
号用户互相直接连接。
-
输出描述
输出
M
用户在
k
跳范围内的影响力
示例一
输入
5 0 2
0 1
1 2
2 3
3 4
4 0
输出
4
示例二
输入
8 0 3
0 1
0 2
0 3
3 4
2 5
5 4
2 3
1 5
输出
5
时空限制
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
解题思路
本题是一个非常典型的图搜索问题，可以直接将输入转化为邻接表来完成。
类似的题目有LC841. 钥匙和房间
其问题转变为，
从原点
M
出发，距离为
k
的点一共有多少个
？
由于规定了距离
k
，因此应该着重考虑使用BFS来解决问题，而不太适合使用DFS来解决了。
换个表达就是，从原点
M
出发，向外搜索
k
层，一共能够搜索到多少个点？
所以直接套上BFS代码的模板就可以完成。
在每一层的搜索中，
k
都会递减
1
，直到
k
小于
0
停止搜索，完成了
k
层搜索。
有很多人写了DFS版本的代码，这是一种错误的做法。
感兴趣的同学也可以尝试DFS的写法，很容易漏计或者超时。
代码
Python
from collections import defaultdict, deque
# 输入连接数n，起始节点m，步数k
n, m, k = map(int, input().split())
# 初始化邻接表
neighbor_dict = defaultdict(list)
# 输入边的情况
for _ in range(n):
# 获得某一条无向边的两个节点，a和b
a, b = map(int, input().split())
# a的近邻节点包含b，b的近邻节点包含a
neighbor_dict[a].append(b)
neighbor_dict[b].append(a)
# 答案变量，记录范围k内的个数
ans = 0
# 初始化用于bfs过程的队列q
q = deque()
q.append(m)
# 用于检查元素是否重复的集合check_set
check_set = set()
# check_set中初始包含起始节点m
check_set.add(m)
# 进行bfs，由于只需要起始节点m考虑最近的k层节点
# 所以当k大于0的时候，持续进行bfs
# 在每层bfs中，k会减小
while k >= 0:
# 搜索层数-1
k -= 1
# 当前层的遍历，获得当前队列长度qSize
# 循环qSize次
qSize = len(q)
# 所有q中的元素，都是距离起始点m的k步内的元素
# ans增加qSize
ans += qSize
for _ in range(qSize):
# 弹出当前队头元素
cur = q.popleft()
# 遍历cur的所有近邻节点nxt
for nxt in neighbor_dict[cur]:
# 如果nxt尚未检查过，则可以加入队列
# 同时标记nxt为已检查过
if nxt not in check_set:
q.append(nxt)
check_set.add(nxt)
# 需要排除掉起始点m本身，所以最终答案需要-1
print(ans-1)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入连接数n，起始节点m，步数k
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
// 初始化邻接表
Map> neighborDict = new HashMap<>();
// 输入边的情况
for (int i = 0; i int a = scanner.nextInt();
int b = scanner.nextInt();
// 将a的近邻节点b加入邻接表
neighborDict.computeIfAbsent(a, key -> new ArrayList<>()).add(b);
neighborDict.computeIfAbsent(b, key -> new ArrayList<>()).add(a);
}
// 答案变量，记录范围k内的个数
int ans = 0;
// 初始化用于bfs过程的队列q
Queue q = new LinkedList<>();
q.add(m);
// 用于检查元素是否重复的集合checkSet
Set checkSet = new HashSet<>();
checkSet.add(m);
// 进行bfs，搜索k层节点
while (k >= 0) {
k--;
int qSize = q.size();
ans += qSize;
for (int i = 0; i int cur = q.poll();
// 遍历cur的所有近邻节点nxt
for (int nxt : neighborDict.getOrDefault(cur, new ArrayList<>())) {
if (!checkSet.contains(nxt)) {
q.add(nxt);
checkSet.add(nxt);
}
}
}
}
// 需要排除掉起始点m本身，所以最终答案需要-1
System.out.println(ans - 1);
}
}
C++
#include
