某公司开项目讨论会,要求每名参会员工均发言,为了不冒犯职位级别高的员工,规定按职位级别高低顺序发言,级别高的员工先发言,级别低的员工后发言。但该公司职级系统非常混乱,目前只知道部分员工间的上下级关系,主持人很难找到一个全局的、合理的发言顺序。请编写程序帮助会议主持人确定一个合理的发言顺序。假定有n名参会人员,编号为0至n-1。 输入格式: 输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过100,表示已知的两名员工的级别关系,每行为两个整数a和b,表示员工a是员工b的上级。 输出格式: 输出为1行整数,每个整数后一个空格,为n名员工的编号,表示n名员工的发言顺序,如果有多种可能的顺序,则输出字典序最小者。 注:字典序,即对象在字典中的顺序。对于两个数字序列,从第一个数字开始比较,当某一个位置的数字不同时,该位置数字较小的序列,字典序较小,例如1239比1245小。c++代码
时间: 2023-09-20 07:05:53 浏览: 43
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 310;
int n, e;
int indeg[N], h[N], e_idx;
int f[N], g[N], h_cnt[N];
struct Edge {
int to, ne;
}edge[N * N];
void add(int a, int b) {
edge[e_idx] = {b, h[a]};
h[a] = e_idx++;
}
bool check(vector<int>& a, vector<int>& b) {
for (int i = 0; i < min(a.size(), b.size()); i++) {
if (a[i] < b[i]) return true;
else if (a[i] > b[i]) return false;
}
return a.size() < b.size();
}
int main() {
cin >> n >> e;
for (int i = 1; i <= e; i++) {
int a, b;
cin >> a >> b;
add(b, a);
indeg[a]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (!indeg[i]) q.push(i);
}
while (q.size()) {
auto t = q.front();
q.pop();
f[t] = g[t] + 1;
for (int i = h[t]; ~i; i = edge[i].ne) {
int j = edge[i].to;
g[j] = max(g[j], f[t]);
indeg[j]--;
if (!indeg[j]) q.push(j);
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res = max(res, f[i]);
h_cnt[f[i]]++;
}
cout << res << endl;
vector<int> path[n];
for (int i = 0; i < n; i++) {
path[f[i]].push_back(i);
}
for (int i = 1; i <= res; i++) {
sort(path[i].begin(), path[i].end());
for (int j = 0; j < path[i].size(); j++) {
int k = path[i][j];
vector<int> tt;
for (int t = h[k]; ~t; t = edge[t].ne) {
int l = edge[t].to;
tt.push_back(f[l]);
}
sort(tt.begin(), tt.end());
int p = 0;
while (p < tt.size() && tt[p] <= i) p++;
if (p == tt.size()) {
cout << k << ' ';
} else {
vector<int> tmp;
for (int t = 0; t < p; t++) {
tmp.push_back(g[path[tt[t]][h_cnt[tt[t]]++]]);
}
sort(tmp.begin(), tmp.end());
int pos = 0;
while (pos < tmp.size() && tmp[pos] < i) pos++;
cout << path[tt[pos]][--h_cnt[tt[pos]]] << ' ';
}
}
}
return 0;
}
```