vector<int> eventualSafeNodes(vector<vector<int>> &graph)
时间: 2023-11-12 07:05:49 浏览: 100
graph) {
int n = graph.size();
vector<int> indegrees(n, 0); // indegrees[i] stores the indegree of node i
vector<vector<int>> adjList(n, vector<int>()); // adjList[i] stores the nodes that have an edge from i
queue<int> q; // queue for BFS
// Build adjacency list and indegrees
for (int i = 0; i < n; i++) {
for (int j : graph[i]) {
adjList[i].push_back(j);
indegrees[j]++;
}
}
// Add nodes with indegree 0 to the queue
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0) {
q.push(i);
}
}
// BFS
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int next : adjList[curr]) {
indegrees[next]--;
if (indegrees[next] == 0) {
q.push(next);
}
}
}
// Add nodes with indegree 0 to the result
vector<int> res;
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0) {
res.push_back(i);
}
}
return res;
}
阅读全文