用C++实现这个问题:7-3 发言顺序 分数 15 作者 朱允刚 单位 吉林大学 某公司开项目讨论会,要求每名参会员工均发言,为了不冒犯职位级别高的员工,规定按职位级别高低顺序发言,级别高的员工先发言,级别低的员工后发言。但该公司职级系统非常混乱,目前只知道部分员工间的上下级关系,主持人很难找到一个全局的、合理的发言顺序。请编写程序帮助会议主持人确定一个合理的发言顺序。假定有n名参会人员,编号为0至n-1。 输入格式: 输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过1
时间: 2023-12-03 17:42:06 浏览: 293
以下是C++的实现代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 305;
int n, e;
int indegrees[maxn]; // 入度
vector<int> adj[maxn]; // 邻接表
void topological_sort() {
queue<int> q;
int cnt = 0; // 计数器,记录已经排序的节点数
for (int i = 0; i < n; ++i) {
if (indegrees[i] == 0) { // 入度为0的节点入队
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出排序结果
++cnt;
for (int i = 0; i < adj[u].size(); ++i) { // 搜索相邻节点
int v = adj[u][i];
--indegrees[v]; // 将相邻节点的入度减1
if (indegrees[v] == 0) { // 如果相邻节点的入度变为0,则加入队列
q.push(v);
}
}
}
if (cnt < n) { // 如果排序的节点数小于总节点数,说明有环
cout << "There is a cycle in the graph." << endl;
}
}
int main() {
cin >> n >> e;
for (int i = 0; i < e; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v); // 添加边
++indegrees[v]; // 将相邻节点的入度加1
}
topological_sort();
return 0;
}
```
该程序使用拓扑排序算法求解,并输出排序结果。如果排序的节点数小于总节点数,说明有环。
阅读全文