BFS 从有向图 G=(V, E)

Question

我想找到无法到达的 s-t-Paths 并获得时间复杂度为 O(mn) 的算法。

我的想法是用 BFS 解决它，因为 DFS 可能会陷入循环。

> Queue Q;
> 
> Reach[][] = bool[|S|][|T|];
> 
> For w in (s, w) in E:
>     if w in T:
>         Reach[s][w] = 1;
>     Q.enqueue(w);
>     w.sources.add(s);
> 
> 
> While Q != empty:
>     v = Q.dequeue();
>     forall w \in (v, w) in E:

>         w.sources.add(s);
>         if w in T:
>             Reach[v][w] = 1;
> 
> print(not(Reach));

这个算法正确吗？

现在我知道BFS的时间复杂度是O(|V| + |E|)。

现在令 m 为 |S| n 是 |T|。 那么我们的时间复杂度就是 O(|V| + |E| + mn)，对吧？ 因为 not(Reach) 必须迭代 m*n 组合？

我如何证明这个算法的正确性？

感谢您的帮助。也许有人知道我可以阅读的此类问题的好资源。 可能是图论书籍。

我尝试实现 BFS 算法，并尝试阅读 BFS 背后的理论。