图

可以终止的点

找到图中所有可以最终抵达出度为零的点的点。

这些点必须在环上的点后，而拓扑排序可以检测所有环上的点以及环后的点。因此只需要先将图取反，再做拓扑排序，就可以只拿到环后的点。时间复杂度\(O(n+m)\)。

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        // reversed graph
        int N = graph.size();
        vector<vector<int>> rgraph(N);
        for (int i = 0; i < N; i++) {
            for (int j: graph[i]) {
                rgraph[j].push_back(i);
            }
        }
        // toposort
        vector<int> ind(N);
        for (int i = 0; i < N; i++) ind[i] = graph[i].size();
        vector<int> ans;
        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (ind[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int p = q.front(); q.pop();
            ans.push_back(p);
            for (int i: rgraph[p]) {
                if (--ind[i] == 0) q.push(i);
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

更巧妙的做法是直接DFS标记状态：默认状态为不安全，从而利用环上递归的特点，将整个环判定为不安全。时间复杂度\(O(n+m)\)。

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> v(graph.size(), 0);

        function<bool(int)> issafe = [&](int x) -> bool {
            if (v[x]) return v[x] == 2;
            v[x] = 1;
            for (int y: graph[x]) {
                if (!issafe(y)) return false;
            }
            v[x] = 2;
            return true;
        };

        vector<int> ans;
        for (int i = 0; i < graph.size(); i++) {
            if (issafe(i)) ans.push_back(i);
        }

        return ans;
    }
};

遍历所有节点的最短路

求一个无向图可从任意节点出发、可重复经过节点的遍历所有节点的路径的最短长度。

NP问题，时间复杂度最优\(O(n^22^n)\)。最短路可以通过BFS求解，但这里的状态不只包含当前节点，还包含已经经过的节点，可以通过状态压缩记录。

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size(); // <= 12
        int S = pow(2, n) - 1;
        // state compression + bfs
        queue<tuple<int, int, int>> q;
        vector<vector<int>> v(n, vector<int>(S+1, 0)); // faster than set<tuple<int,int>>
        for (int i = 0; i < n; i++) {
            q.emplace(i, 1 << i, 0); // emplace is faster than push
            v[i][1 << i] = 1; // always set to vis right after push
        }
        while (!q.empty()) {
            auto [p, s, d] = q.front(); q.pop();
            //cout << p << " " << bitset<12>(s).to_string() << " " << d << endl;
            if (s == S) return d;
            for (int next_p: graph[p]) {
                int next_s = s | (1 << next_p);
                if (!v[next_p][next_s]) {
                    q.emplace(next_p, next_s, d+1);
                    v[next_p][next_s] = 1;
                }
            }
        }
        return -1;
    }
};