解释vector<int> eventualSafeNodes(vector<vector<int>> &graph)
时间: 2023-10-22 14:34:21 浏览: 44
Graph)函数的作用
vector<int> eventualSafeNodes(vector<vector<int>> Graph)函数的作用是寻找一个有向图中所有“终止安全节点”,即一个节点在该图中的所有路径中不会出现环。该函数的输入参数是一个由vector<int>类型的数组组成的二维数组Graph,其中Graph[i]表示节点i的出边集合。函数的返回值是一个vector<int>类型的数组,其中包含所有终止安全节点的编号。
相关问题
vector<int> eventualSafeNodes(vector<vector<int>> &graph)
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;
}
typedef pair<int,int>pii;vector<pii>graph[N];改写成普通的方式
这段代码可以改写成以下的普通方式:
```
#include <vector>
#include <utility> // for std::pair
const int N = 100; // 假设 N = 100
typedef std::pair<int, int> pii;
std::vector<pii> graph[N];
```
其中,`std::pair`是C++标准库中的一个模板类,用来表示一对值,这里用来表示两个整数。`std::vector`是C++标准库中的一个模板类,表示动态数组。这里使用了模板参数`<pii>`,表示这个vector中存储的是`std::pair<int, int>`类型的数据。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)