某公司开项目讨论会,要求每名参会员工均发言,为了不冒犯职位级别高的员工,规定按职位级别高低顺序发言,级别高的员工先发言,级别低的员工后发言。但该公司职级系统非常混乱,目前只知道部分员工间的上下级关系,主持人很难找到一个全局的、合理的发言顺序。请编写程序帮助会议主持人确定一个合理的发言顺序。假定有n名参会人员,编号为0至n-1。输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过100,表示已知的两名员工的级别关系,每行为两个整数a和b,表示员工a是员工b的上级。输出为1行整数,每个整数后一个空格,为n名员工的编号,表示n名员工的发言顺序,如果有多种可能的顺序,则输出字典序最小者。 注:字典序,即对象在字典中的顺序。对于两个数字序列,从第一个数字开始比较,当某一个位置的数字不同时,该位置数字较小的序列,字典序较小,例如1239比1245小。给出C++代码
时间: 2023-09-20 18:05:53 浏览: 195
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int n, e;
int h[N], e_idx; // 邻接表存储上下级关系
int d[N]; // 入度
vector<int> res; // 存储答案
struct Node {
int id, val; // 职位编号和字典序
bool operator< (const Node& t) const {
return val > t.val || (val == t.val && id > t.id); // 优先级:职位编号小的,字典序小的
}
};
void add(int a, int b) {
h[a] = ++e_idx;
d[b]++;
}
void topsort() {
priority_queue<Node> q; // 优先队列存储可发言的职位
for (int i = 0; i < n; i++) {
if (d[i] == 0) {
q.push({i, i}); // 初始入队
}
}
while (!q.empty()) {
auto t = q.top(); q.pop();
res.push_back(t.id); // 存储答案
for (int i = 0; i < n; i++) {
if (h[t.id] == 0 || h[t.id] == i) continue; // 没有上下级关系 或 不是下级
if (--d[i] == 0) {
q.push({i, t.val}); // 下级入队,字典序不变
}
}
}
}
int main() {
cin >> n >> e;
for (int i = 0; i < e; i++) {
int a, b; cin >> a >> b;
add(a, b);
}
topsort();
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
return 0;
}
```
阅读全文