-
Notifications
You must be signed in to change notification settings - Fork 0
/
210.php
58 lines (48 loc) · 1.4 KB
/
210.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<?php
class Solution {
/**
* @param Integer $numCourses
* @param Integer[][] $prerequisites
* @return Integer[]
*/
function findOrder($numCourses, $prerequisites)
{
if ($numCourses <= 0) return [];
$in_degree = [];
$graph = [];
$queue = [];
foreach ($prerequisites as $prerequisite) {
$graph[$prerequisite[1]][] = $prerequisite[0];
if (!isset($in_degree[$prerequisite[0]])) $in_degree[$prerequisite[0]] = 0;
$in_degree[$prerequisite[0]] ++;
}
for ($i = 0; $i < $numCourses; $i ++) {
if (!isset($in_degree[$i])) {
$queue[] = $i;
}
}
$res = [];
while ($queue) {
$node = array_shift($queue);
$res[] = $node;
if (!isset($graph[$node])) {
continue;
}
$next_courses = $graph[$node];
foreach ($next_courses as $next_course) {
$in_degree[$next_course] --;
if ($in_degree[$next_course] == 0) {
$queue[] = $next_course;
}
}
}
if (count($res) == $numCourses) {
return $res;
}
return [];
}
}
$sol = new Solution();
$numCourses = 4;
$prerequisites = [[1,0],[2,0],[3,1],[3,2]];
var_export($sol->findOrder($numCourses, $prerequisites));