需要安排事件的顺序
需要安排事件的顺序
提问于 2019-11-06 15:35:06
在一次编码采访中，我被问到了这个问题，我尝试了hashmap、堆树和队列，但是没有什么效果。我想知道我错过了什么，有人能告诉我如何处理这个问题吗？
描述是2050年。自2045年以来，隐形传送就已成为可能。现在你刚给自己买了一台传送机。然而。操作这台机器不是儿戏。才能传送到其他地方。你得在机器上做些安排。机器中有N个需要打开的设备，不同设备之间存在M型依赖关系。现在你需要弄清楚打开设备的顺序，这样机器才能启动。
输入·第一线将包含两个数字:n表示机器中设备的数量。M表示设备依赖的数目。
下一个M行包含两个整数A和B，表示从A到B的依赖关系(这意味着A必须打开以启动B。)
输出·在单行上，打印顺序(用空间分隔)，其中机器应该打开以进行传送。约束条件
• 1 <= N <= 500
• 1 <= M = N(N-1)/2
• 1 <= A <= 500
• 1 < B <= 500示例测试用例解决方案输入：
6 6
1 2
1 3
2 5
3 4
5 6
4 6样本输出
1 3 4 2 5 6解释
如果你遵循这个模式。您将观察到，要打开设备6。您需要打开4和5。要打开设备4和5。我们需要分别打开设备3和2。最后，要打开设备3和2，我们需要打开设备1。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-11-06 16:18:59
Stack Overflow用户
发布于 2019-11-06 16:08:08
这是一个叫做拓扑排序的经典问题。
计算启动每台机器所需的机器数量。
关于你的案子：
cnt1 =0
cnt2 =1 //机器1
cnt3 =1 //机器1
cnt4 =1 //机器3
cnt5 =1 //机器2
cnt6 =2 //机器4，5
如果it不等于0，就意味着这台机器可以打开。
像这样的事情应该有效：
queue<int> q;
for (int i = 1; i <= n; i++)
if (cnt[i] == 0) q.push(i);
while (!q.empty()) {
int id = q.front(); q.pop(); // Turn on machine id
print (id)
for (int i = 0; i < dep[id].size(); i++) { // Dependencies for machine id
cnt[dep[id][i]]--;
if (cnt[dep[id][i]] == 0)
q.push(dep[id][i]);
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58733675
复制相关文章
相似问题
腾讯云开发者
