Solution1 拓扑排序 + 反向图

  • 时间复杂度 O(m + n)

  • 空间复杂度 O(m + n)

一个节点如果在环里面,则是不安全的。反之则是安全的。

我们要找的即为出度为 0 的点(即安全节点),以及所指向的节点仅包含安全节点的节点。

而拓扑排序找的是入度为 0 的节点,以及由入度为 0 的节点组成的节点。

我们首先构建反向图,然后再用拓扑排序加入入度为 0 的节点即可。在环中的节点不可能加到 topsort 的 que 里去。

Last updated