題目： LeetCode - 802. Find Eventual Safe States

題目說明

有 n 個 node 組成一個單向圖，編號 0 ~ n - 1，給一個二維陣列 graph，每個 index 之陣列裡面所含的數字表編號 index 的 node 含有至該數字的單向邊，如題目 Example 所示。

若某個 node 不含任何連向外部的邊稱為 terminal node，而若某個 node 連向外部的所有路徑皆可通往任一 terminal node 或 safe node 則稱為 safe node。

求 0 ~ n - 1 中所有 safe node 的編號為何。

解題思路

直覺第一想法是遍歷每個 node 用 DFS 判斷是否所有路徑皆能走到任一 terminal node 或 safe node，其中若含有任何 loop 表起點的 node 勢必不為 safe node，最後加上 map 紀錄檢查過的 node 做剪枝。

參考解法

此解法效率以及空間使用率皆不佳，若將容器換成靜態或一次性擴增，減少擴增及查詢的時間，可進一步提升。

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
class Solution {
private:
    set<int> traveled;
    map<int, bool> isSafeNode;

    // return true if node idx is a safe node
    bool dfs(int idx, vector<vector<int>>& graph) {
        if (isSafeNode.count(idx)) {
            return isSafeNode[idx];
        }

        bool isSafe = true;
        traveled.insert(idx);

        if (!graph[idx].empty()) {
            for (const auto& nextNode : graph[idx]) {
                // if there have any loops,
                // this node must not be a safe node
                if (traveled.count(nextNode) ||
                        !dfs(nextNode, graph)) {
                    isSafe = false;
                    break;
                }
            }
        }

        traveled.erase(idx);
        isSafeNode[idx] = isSafe;
        return isSafe;
    }

public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> safeNodes;
        for (int i = 0; i < graph.size(); ++i) {
            if (dfs(i, graph)) {
                safeNodes.push_back(i);
            }
        }
        return safeNodes;
    }
};