输入格式: 输入第一行为两个整数n和e,均不超过300。n表示参会人员数。接下来e行,e不超过100,表示已知的两名员工的级别关系,每行为两个整数a和b,表示员工a是员工b的上级。 输出格式: 输出为1行整数,每个整数后一个空格,为n名员工的编号,表示n名员工的发言顺序,如果有多种可能的顺序,则输出字典序最小者。 注:字典序,即对象在字典中的顺序。对于两个数字序列,从第一个数字开始比较,当某一个位置的数字不同时,该位置数字较小的序列,字典序较小,例如1239比1245小。c++
时间: 2023-09-19 09:13:26 浏览: 109
这是一道拓扑排序的经典题目,可以使用BFS或DFS实现。以下是使用BFS实现的示例代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 305;
struct Employee {
int id, level;
};
vector<int> adj[MAXN];
int inDegree[MAXN];
bool visited[MAXN];
Employee employees[MAXN];
bool cmp(Employee a, Employee b) {
return a.id < b.id;
}
vector<int> topologicalSort(int n) {
queue<int> q;
vector<int> ans;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
ans.push_back(u);
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
return ans;
}
int main() {
int n, e;
cin >> n >> e;
for (int i = 1; i <= n; i++) {
employees[i].id = i;
cin >> employees[i].level;
}
sort(employees + 1, employees + n + 1, cmp);
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
adj[b].push_back(a);
inDegree[a]++;
}
vector<int> ans = topologicalSort(n);
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
return 0;
}
```
代码思路:
首先定义一个结构体 Employee,表示员工的编号和级别。然后将所有员工按照编号从小到大排序,以便输出时能够按照字典序输出。
接着输入每个员工的级别和已知的上下级关系,用邻接表存储图,同时统计每个节点的入度。
最后使用BFS实现拓扑排序,将排序结果输出即可。
阅读全文