LeetCode-PHP/802.php at master · HugoWen/LeetCode-PHP · GitHub

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
<?php


class Solution {

    public $state = [];

    /**
     * @param Integer[][] $graph
     * @return Integer[]
     */
    function eventualSafeNodes($graph)
    {

        if (!$graph) return [];

        $ret = [];

        for ($i = 0; $i < count($graph); $i ++) {
            if ($this->dfs($graph, $i)) {
                $ret[] = $i;
            }
        }

        return $ret;

    }

    function dfs($graph, $start)
    {
        if (isset($this->state[$start])) return $this->state[$start] == 1;

        $this->state[$start] = 0;
        foreach ($graph[$start] as $next) {
            if (!$this->dfs($graph, $next)) {
                return false;
            }
        }

        $this->state[$start] = 1;
        return true;
    }
}

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
$sol = new Solution();
var_dump($sol->eventualSafeNodes($graph));