从Leetcode 每日一题练习继续讨论：
802. 找到最终的安全状态
802. Find Eventual Safe States
题解
本题先考虑如何找到终结节点，根据题目如果一个节点上没有出边那么该节点就为终结节点，则遍历graph，所有没有出边的下标对应的节点均为终结节点。在遍历graph时，既可以得到所有节点对应的后继节点，也可以得到所有节点对应的全部前置节点，则对全部的终结节点，将其全部放入队列，遍历其全部的前置节点，这些节点均有指向终结节点的有向边，可能为安全节点，判断这些节点是否为安全节点，如果是则更新安全节点的状态数组，并将该节点放入队列中。不是则跳过继续向后遍历。如此反复即可得到全部安全节点。
这种方式可以得到结果的关键在于，以终结节点作为终点反向进行拓扑排序，先遍历到的指向终结节点的节点中只有仅包含指向终结节点一条边的节点会被认为是安全节点，再继续遍历得到的这些安全节点的前置节点，就可得到仅指向这些安全节点的或者同时指向安全节点和终结节点的新的安全节点，相当于每次都在得到新的安全节点的基础上在可能变为安全节点的节点中寻找哪些是新的安全节点。
本题也可以构造一个反向图，将原图中全部的边反向，则终结节点此时变为起始节点，遍历这些起始节点的后续节点，删掉起始节点和后续节点之间的边，找到所有入度变为0的节点即为安全节点，再在这些节点的基础上继续向后遍历反向图中的后续节点，执行同样的操作，每次都找到入度变为0的节点继续遍历，如此反复直到无法继续遍历即得全部安全节点。
代码
class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<int>> prevNodes(n);
vector<bool> canReachTerminal(n, false);
vector<int> terminalNodes;
// 找出终结节点并构建前置节点关系
for(int i = 0; i < n; i++) {
if(graph[i].empty()) {
terminalNodes.push_back(i);
canReachTerminal[i] = true;
}
// 构建前置节点关系
for(int next : graph[i]) {
prevNodes[next].push_back(i);
}
}
queue<int> q;
for(int node : terminalNodes) {
q.push(node);
}
while(!q.empty()) {
int curr = q.front();
q.pop();
// 遍历当前节点的所有前置节点
for(int prev : prevNodes[curr]) {
if(!canReachTerminal[prev]) {
// 检查prev的所有后继节点是否都可以到达终结节点
bool allNextCanReach = true;
for(int next : graph[prev]) {
if(!canReachTerminal[next]) {
allNextCanReach = false;
break;
}
}
if(allNextCanReach) {
canReachTerminal[prev] = true;
q.push(prev);
}
}
}
}
vector<int> result;
for(int i = 0; i < n; i++) {
if(canReachTerminal[i]) {
result.push_back(i);
}
}
return result;
}
};