上面提供的代码有问题,请修改
时间: 2024-03-03 22:51:16 浏览: 24
非常抱歉,我的回答有误。以下是修正后的代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class adjListGraph {
private:
int n; // 顶点数量
vector<int> *adj; // 邻接表
int *indegree; // 入度数组
public:
adjListGraph(int n) {
this->n = n;
adj = new vector<int>[n];
indegree = new int[n];
for (int i = 0; i < n; i++)
indegree[i] = 0;
}
// 添加一条边
void addEdge(int u, int v) {
adj[u].push_back(v);
indegree[v]++;
}
// 拓扑排序判断是否存在环,并返回拓扑序列
vector<int> noLoop() {
vector<int> res;
queue<int> q; // 存储入度为 0 的顶点
for (int i = 0; i < n; i++)
if (indegree[i] == 0)
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
res.push_back(u);
for (int v : adj[u]) {
indegree[v]--;
if (indegree[v] == 0)
q.push(v);
}
}
if (res.size() == n)
return res;
else
return vector<int>();
}
};
int main() {
int n;
cin >> n;
adjListGraph g(n);
for (int i = 0; i < n; i++) {
int u, v;
char comma;
cin >> u >> comma >> v;
g.addEdge(u - 1, v - 1);
}
vector<int> res = g.noLoop();
if (!res.empty()) {
for (int u : res)
cout << u + 1 << " ";
} else {
cout << "loop";
}
return 0;
}
```
在上述代码中,我们定义了一个 adjListGraph 类,它包含了有向图的邻接表表示以及拓扑排序算法的实现。在主函数中,我们首先读入输入数据,并使用邻接表表示有向图。然后,我们调用 adjListGraph 类的 noLoop 函数来进行拓扑排序,判断该有向图是否存在环。如果拓扑排序成功,我们就可以输出拓扑序列;否则,输出字符串 “loop”。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)