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-02 20:03:38 浏览: 49
可以使用拓扑排序来解决这个问题。
首先,将每个节点的入度(即有多少个节点指向该节点)计算出来,然后找到入度为 0 的节点,将其加入结果数组中,并将其指向的节点的入度减 1。重复这个过程,直到所有节点都被加入结果数组中或者不存在入度为 0 的节点。
以下是 PHP 代码实现:
```
function findOrder($numCourses, $prerequisites) {
$indegrees = array_fill(0, $numCourses, 0); // 初始化所有节点的入度为 0
// 计算所有节点的入度
foreach ($prerequisites as $pair) {
$indegrees[$pair[0]]++;
}
$queue = []; // 存储入度为 0 的节点
$result = []; // 存储结果数组
// 将所有入度为 0 的节点加入队列中
for ($i = 0; $i < $numCourses; $i++) {
if ($indegrees[$i] == 0) {
array_push($queue, $i);
}
}
// 开始拓扑排序
while (!empty($queue)) {
$node = array_shift($queue);
array_push($result, $node);
foreach ($prerequisites as $pair) {
if ($pair[1] == $node) {
$indegrees[$pair[0]]--;
if ($indegrees[$pair[0]] == 0) {
array_push($queue, $pair[0]);
}
}
}
}
// 如果存在入度不为 0 的节点,则说明图中存在环,返回空数组
foreach ($indegrees as $degree) {
if ($degree != 0) {
return [];
}
}
return $result;
}
```
对于输入 `[[1,0],[2,1]],3`,输出为 `[0,1,2]`;对于输入 `[[1,0],[2,1]],4`,输出为 `[0,1,2,3]`;对于输入 `[[1,0],[0,1]],2`,输出为 `[]`。