php“输入[[1,0],[2,1]],3输出[0,1,2],输入[[1,0],[2,1]],4输出[0,1,2,3],输入[[1,0],[0,1]],2输出[]
时间: 2023-10-04 10:08:52 浏览: 46
这道题可以使用拓扑排序来解决。
首先,我们需要根据输入构建一个图。对于输入 [[1,0],[2,1]],我们可以将它表示为以下图形:
```
0 -> 1 -> 2
```
其中箭头表示有向边,数字表示节点。节点 0 没有任何入边,所以它是一个起点。节点 2 没有任何出边,所以它是一个终点。
接着,我们需要对这个图进行拓扑排序。拓扑排序可以保证,如果有一条从节点 A 到节点 B 的有向边,那么在排序后,节点 A 一定在节点 B 的前面。
我们可以使用一个队列来进行拓扑排序。首先将所有入度为 0 的节点加入队列中。接着,从队列中取出一个节点,将它的出边的所有节点的入度减 1。如果减完之后某个节点的入度变成了 0,那么就将这个节点加入队列。重复这个过程,直到队列为空。
最后,我们得到的拓扑排序结果就是可行解。如果某个节点没有出现在拓扑排序结果中,那么它就不可达。
对于输入 [[1,0],[2,1]],拓扑排序的结果为 0 -> 1 -> 2,因此可行解为 [0, 1, 2]。对于输入 [[1,0],[0,1]],没有任何节点的入度为 0,所以不存在可行解,应该返回空数组 []。
以下是 PHP 代码实现: