难度: Medium
Submission
运行时间: 45 ms
内存: 19.2 MB
class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
g=[[]for _ in range(n)]
cnt=[0]*n
for u,v in edges:
g[v].append(u)
cnt[u]+=1
if cnt[destination]!=0:
return False
dq=deque()
dq.append(destination)
while dq:
cur=dq.popleft()
if cur==source:
return True
for nex in g[cur]:
cnt[nex]-=1
if cnt[nex]==0:
dq.append(nex)
return False
Explain
该题解采用了逆向拓扑排序的方法来解决问题。首先，根据输入的边构建了一个逆向的邻接表，即对于每个边(u, v)，在邻接表中v指向u。同时，使用一个计数器数组来记录每个节点入边的数量。如果终点destination的入边不为0，直接返回False，因为终点不应该有出边。之后使用一个队列来进行逆向拓扑排序，从终点开始，每次从队列中取出一个节点，检查该节点是否为始点source，是则返回True。对于该节点的每个邻居，减少它的入边计数，并在入边计数为0时将其加入队列。如果队列处理完，始点未被访问到，则返回False。这个方法主要是检查是否存在从source到destination的有效路径。
时间复杂度: O(V + E)
空间复杂度: O(V)
class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# 创建逆向邻接表
g=[[] for _ in range(n)]
# 创建入边计数器
cnt=[0]*n
# 填充逆向邻接表和入边计数器
for u, v in edges:
g[v].append(u)
cnt[u]+=1
# 检查终点是否有入边
if cnt[destination]!=0:
return False
# 初始化队列，开始从终点逆向拓扑排序
dq=deque()
dq.append(destination)
while dq:
cur=dq.popleft()
# 检查当前节点是否是起点
if cur==source:
return True
# 遍历当前节点的所有邻居
for nex in g[cur]:
cnt[nex]-=1
# 当邻居的入边计数为0时，加入队列
if cnt[nex]==0:
dq.append(nex)
# 如果队列处理完还没找到起点，返回False
return False
Explore
在构建逆向邻接表的时候，选择将每个边(u, v)存储为v指向u是为了实现逆向拓扑排序。逆向拓扑排序是从终点开始，逐步退回到起点的过程。通过将边逆向存储，我们可以从终点开始，沿着逆向的边移动，逐步退回到起点。这种方法可以在不追踪已访问节点的情况下，验证是否存在一条从起点到终点的有效路径。
逆向拓扑排序在此题中的作用是从终点开始，逐步检查每个可到达的节点，直到到达起点或者无更多节点可访问。通过这种方式，我们可以有效地确认是否存在一条从起点到终点的路径。在逆向拓扑排序过程中，我们使用一个入边计数器来管理每个节点的入边数量。只有当一个节点的所有入边都被访问过（即入边计数为0时），这个节点才会被加入到处理队列中。这确保了我们按照正确的顺序访问节点，从而可以正确地验证从起点到终点的路径是否存在。
在检查终点destination时，如果其入边不为0则直接返回False，因为在一个有效的有向无环图中，终点不应有任何出边（即没有其他节点指向终点之外的节点）。如果终点的入边计数不为0，说明存在指向终点的边，这违背了终点应是图中最后一个节点的特性。因此，如果终点的入边计数不为0，我们可以断定不存在一条有效的从起点到终点的路径，因此返回False。