有了上面的两个前提的话,我们继续来分析。如果环的大小大于 3,那么存在 A 无法追到 B 的可能。这个可能仅在 A 到环的入口的距离大于 B 到环的入口的距离 + 1。如果不满足这个条件,那么 A 一定可以追到 B。
之所以 + 1 是因为 A 先走 B 后走。
由于 B 尽量会让自己尽可能晚一点被抓到,那么 B 一定会去一个点,这个点满足:B 比 A 先到。(否则 B 还没到就被抓到了,即根本到不了)。满足条件的点可能不止一个,B 一定会去这些点中最晚被抓住的。最晚被抓住其实就等价于 A 到这个点的距离减去 B 到这个点的距离。由于游戏需要我们返回回合数,那么直接返回 A 到这个点的距离其实就可以了。
以上两个都是图的基本操作,也就是模板,不再赘述。不过对于检测环的入口来说,这个有点意思。检测环的入口,我们可以通过对 B 做 BFS,当 B 到达第一个环上的节点,就找到了环的入口。有的同学可能会问,如果 B 一开始就在环上呢?实际上,我们可以认为 B 在的节点就是环的节点, 这对结果并没有影响。
为了更快地找到一个节点的所有邻居,我们需要将题目中给的 edges 矩阵转化为临接矩阵。
关键点
明确这道题中有且仅有一个环
当且仅当环的长度大于 3,A 到环入口的距离大于 B 到环入口的距离 + 1 才永远追不上
如何检测环,如果计算单点到图中所有点的距离
代码
语言支持:Python3
Python3 Code:
classSolution:defchaseGame(self,edges: List[List[int]],startA:int,startB:int) ->int: n =len(edges) graph = collections.defaultdict(list)for fr, to in edges: graph[fr].append(to) graph[to].append(fr)defbfs(fr,find_entry=False): dist = collections.defaultdict(lambda: float("inf")) q = collections.deque([fr]) steps =0nonlocal entrywhile q:for i inrange(len(q)): cur = q.popleft()if cur in dist:continueif find_entry and cur in circle: entry = curreturn dist[cur]= stepsfor neibor in graph[cur]: q.append(neibor) steps +=1return dist parent ={} depth = collections.defaultdict(int)# 可以被用作 visited circle =set() entry =0# 环的入口defcal_circle(node,p): parent[node]= p depth[node]= depth[p]+1for neibor in graph[node]:if neibor == p:continueif neibor notin depth:cal_circle(neibor, node)elif depth[neibor]< depth[node]:# 检测到了环 cur = nodewhile cur != neibor: circle.add(cur) cur = parent[cur] circle.add(neibor)cal_circle(1, 0) d1, d2 =bfs(startA),bfs(startB)bfs(startB, True)iflen(circle)>3:if d1[entry]> d2[entry]+1:return-1if d1[startA]==1:return1 ans =1for i inrange(1, n +1):if d1[i]- d2[i]>1: ans =max(ans, d1[i])return ans