安全状态

思路

建图后,需要判断一次深搜路径上有无重复点出现,并用涂色法记录整条路径上的安全或者不安全状态。


class Solution {
public: 
    int n = 0;
    vector<int> to, next, head;
    int headpos = 0;
    vector<int> vis;
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        n = graph.size();
        head.resize(n);
        vis.resize(n);
        // to.resize(100000);
        // next.resize(100000);

        for(int u = 0; u < n; u++) {
            vector<int> &vec = graph[u];
            to.resize(to.size() + vec.size() + 1);
            next.resize(next.size() + vec.size() + 1);
            
            for(auto &v : vec) {
                headpos++;
                to[headpos] = v;
                next[headpos] = head[u];
                head[u] = headpos;
            }
        }

        vector<int> vec;
        for(int u = 0; u < n; u++) {
            if(findEnd(u) > 0) {
                vec.push_back(u);
            }
        }
        return vec;
    }

    int findEnd(int u) {
        if(vis[u] != 0)
            return vis[u];
        vis[u] = -1;
        
        for(int i = head[u]; i ; i = next[i]) {
            int v = to[i];
            if(findEnd(v) < 0)  return -1;
        }
        vis[u] = 1;
        return 1;
    }
};

Comments