情侣一个月2-3次正常吗?刚开始的时候一周两到3次，女朋友和我的需求不对等～

昨天晚上加班到十点多，突然隔壁组那个小胖冲进来说，“你快给我讲讲，‘最长团队传球连击’那个算法题怎么写啊？明天要面试了我一行都没写出来！”我当时一边漱口一边说，“你说的那个，是不是有点像篮球场上那种——谁能一口气连续传球最多次的玩法？”他点点头。我说那你看，这种题其实套路挺常见的，最核心就是找一条‘最长路径’，不过场景换成了团队和传球嘛。

场景代入下

咱假设现在有n个人在场上，每个人只能传球给固定的某几个人，比如A只能传给B或者C，B又能传给D，类似这种关系吧。你要做的，就是求从某个球员出发，最多能连续传几次球，不能有重复，反正不能自个来回传。其实你仔细想啊，这不就是典型的有向图，然后找一条最长不回头的路么。

正经点说解法哈

我洗完杯子回到工位，随手画了个草图，思路很简单，直接建图，把所有人和他们能传的关系列出来，用邻接表存就行，然后每个人当起点，去DFS暴力试呗，反正不让回头，那就递归搜下去，每到一个新队员就+1，回头就停。最重要的是，要记住已经访问过的，别走回头路，传球不是玩套娃对吧。

就像这样，比如有这么个关系：

team = {
  0: [1, 2],
  1: [2, 3],
  2: [3],
  3: []
}

意思就是0能传给1和2，1能传给2和3，以此类推。那你要做的，其实就是从每个人出发搜一遍，记录最远能走几步。每次搜到新队员都要标记一下，不然走死循环你就炸了。

代码来一段，不废话

我昨天写给小胖的代码，洗完手直接贴给他了，他说看懂了（其实他没懂）：

deflongest_pass(team):
defdfs(player, visited):
        visited.add(player)
        max_chain = 0
for next_player in team.get(player, []):
if next_player notin visited:
                max_chain = max(max_chain, 1 + dfs(next_player, visited))
        visited.remove(player)
return max_chain

    result = 0
for player in team.keys():
        result = max(result, dfs(player, set()))
return result

# 举个例子
team = {
0: [1, 2],
1: [2, 3],
2: [3],
3: []
}
print(longest_pass(team))  # 输出是3，最多能连续传3次

我当时喝着凉水跟小胖解释，你看啊，这个代码其实每个人都轮流当一次“第一传”，然后暴力递归一遍，不让他回头。只要你传的链最长，结果就会被记录下来。不是特别高深，但对于数据量不大的场景，完全够用。面试问原理你就说深度优先搜索，别怕，吹一点就完了。

我那会儿还提醒他一嘴，“你别想着啥记忆化剪枝了，这种题一般不会卡性能，真要大数据量再说。”还有个事儿，像有些题目会给成环关系，这就必须得visited去判重，不然一不小心自个儿给自个儿传球，一晚上都传不完，代码直接卡死。小胖还担心说，“要不要考虑无解？”我说你看，如果没有边，那最长就0嘛，很自然。

你要真遇到实际业务场景，其实就跟打配合一样，有时候传球路线固定，有时候是动态变化，你算法写灵活点就行。其实面试题就图个明白原理，代码干净点，心态放松。