某公司开项目讨论会,要求每名参会员工均发言,为了不冒犯职位级别高的员工,规定按职位级别高低顺序发言,级别高的员工先发言,级别低的员工后发言。但该公司职级系统非常混乱,目前只知道部分员工间的上下级关系,主持人很难找到一个全局的、合理的发言顺序。请编写程序帮助会议主持人确定一个合理的发言顺序。假定有n名参会人员,编号为0至n-1。输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过100,表示已知的两名员工的级别关系,每行为两个整数a和b,表示员工a是员工b的上级。给出C++代码
时间: 2023-12-03 22:43:28 浏览: 196
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 310;
int n, e;
vector<int> g[N];
int in_degree[N]; // 入度
int level[N]; // 级别,也就是发言顺序
void topsort()
{
queue<int> q;
// 将所有入度为0的点入队
for (int i = 0; i < n; i++)
if (in_degree[i] == 0)
q.push(i);
int cur_level = 0; // 当前级别
while (!q.empty())
{
int sz = q.size(); // 记录当前级别的点数
for (int i = 0; i < sz; i++)
{
int u = q.front();
q.pop();
level[u] = cur_level; // 记录级别
for (int j = 0; j < g[u].size(); j++)
{
int v = g[u][j];
in_degree[v]--;
if (in_degree[v] == 0)
q.push(v);
}
}
cur_level++; // 进入下一级别
}
}
int main()
{
cin >> n >> e;
memset(in_degree, 0, sizeof in_degree);
for (int i = 0; i < e; i++)
{
int a, b;
cin >> a >> b;
g[b].push_back(a); // 员工b是员工a的上级,连一条从b到a的边
in_degree[a]++; // a的入度加1
}
topsort();
for (int i = 0; i < n; i++)
cout << level[i] << endl;
return 0;
}
```
阅读全文