关注
第三题: #include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
int m, n, k;
cin >> m >> n >> k;
vector<int> tmp;
map<int, vector<int> > datas; // int为序号,vector为依赖他的结点
for (int i = 0; i <= m; i++) {
vector<int> tmp;
datas[i] = tmp;
}
vector<int> yilai(m + 1, 0); // 结点i是否有依赖,0为无依赖可以直接操作
vector<int> done(m + 1, 0); // 结点i是否已完成,0为未完成
int left, right;
for (int i = 0; i < k; i++) {
cin >> left >> right;
yilai[left] = 1;
datas[right].push_back(left);
}
int ans = 0;
int conutOfDone = 0; // 当前已完成计数
while (conutOfDone != m) {
int conutoftodo = 0;
vector<int> deal;
for (int i = 1; i <= m; i++) {
if (yilai[i] == 0 && done[i] == 0) {
conutoftodo++;
conutOfDone++;
deal.push_back(i); // 存储当前待完成结点,用于更新各数组
}
}
if (conutoftodo == 0 && conutOfDone != n) {
cout << "E" << endl;
return -1;
}
else if (conutoftodo <= n)
ans++;
else if (conutoftodo > n) {
if (conutoftodo % n == 0)
ans = ans + conutoftodo / n;
else
ans = ans + conutoftodo / n + 1;
}
for (int i = 0; i < deal.size(); i++) { // 更新各个数组
done[deal[i]] = 1;
vector<int> ttt = datas[deal[i]];
for (int j = 0; j < ttt.size(); j++)
yilai[ttt[j]] = 0;
}
}
cout << ans << endl;
return 0;
}
查看原帖
点赞 4
相关推荐
投递华为等公司10个岗位 >
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
745843次浏览 11913人参与
# 你的工作大概什么时候入职? #
2476次浏览 33人参与
# 海康威视求职进展汇总 #
94032次浏览 1132人参与
# 百度工作体验 #
23721次浏览 243人参与
# 今年形式下双非本找得到工作吗 #
7311次浏览 157人参与
# 2022届毕业生现状 #
320262次浏览 4435人参与
# 你的秋招进行到哪一步了 #
358389次浏览 6310人参与
# 产品实习,你更倾向大公司or小公司 #
37274次浏览 577人参与
# 非技术岗是怎么找实习的 #
75672次浏览 1413人参与
# 比亚迪求职进展汇总 #
166627次浏览 1235人参与
# 你觉得比亚迪今年还有春招吗? #
46078次浏览 331人参与
# 学历对求职的影响 #
133057次浏览 1510人参与
# 面试等了一周没回复,还有戏吗 #
41081次浏览 501人参与
# 浅聊一下我实习的辛苦费 #
82337次浏览 769人参与
# 国企和大厂硬件兄弟怎么选? #
44990次浏览 851人参与
# 0offer是寒冬太冷还是我太菜 #
416953次浏览 4835人参与
# 铜五铁六真的存在吗? #
28915次浏览 302人参与
# 考研失败就一定是坏事吗? #
20471次浏览 215人参与
# 通信硬件人笔面经互助 #
114623次浏览 2284人参与
# 荣耀求职进展汇总 #
66347次浏览 669人参与