某公司开项目讨论会,要求每名参会员工均发言,为了不冒犯职位级别高的员工,规定按职位级别高低顺序发言,级别高的员工先发言,级别低的员工后发言。但该公司职级系统非常混乱,目前只知道部分员工间的上下级关系,主持人很难找到一个全局的、合理的发言顺序。请编写程序帮助会议主持人确定一个合理的发言顺序。假定有n名参会人员,编号为0至n-1。 输入格式: 输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过100,表示已知的两名员工的级别关系,每行为两个整数a和b,表示员工a是员工b的上级。 输出格式: 输出为1行整数,每个整数后一个空格,为n名员工的编号,表示n名员工的发言顺序,如果有多种可能的顺序,则输出字典序最小者。c++代码
时间: 2023-11-03 11:04:09 浏览: 143
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 310;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int ans[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i ++ )
if (!d[i])
q.push(i);
int cnt = 0;
while (q.size())
{
int t = q.top();
q.pop();
ans[cnt ++ ] = t;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0) q.push(j);
}
}
if (cnt == n) return true;
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
add(b, a); // 注意建反图
d[a] ++ ;
}
if (topsort())
{
for (int i = 0; i < n; i ++ ) cout << ans[i] << ' ';
}
else puts("-1");
return 0;
}
```
阅读全文