关注
第三题: #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
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# xx岗简历求拷打 #
1287次浏览 18人参与
# 金三银四,你有感觉到吗 #
686449次浏览 6063人参与
# 有转正机会的小厂实习值得去吗? #
2181次浏览 33人参与
# 哪些公司开春招了? #
27926次浏览 188人参与
# 你最讨厌面试被问什么 #
3323次浏览 43人参与
# 2024开工大吉 #
26694次浏览 102人参与
# 机械制造2024笔面经 #
1540060次浏览 13005人参与
# 秋招踩过的“雷”,希望你别再踩 #
186952次浏览 1692人参与
# 毕业季等于分手季吗 #
54317次浏览 649人参与
# 牛客租房专区 #
156326次浏览 1734人参与
# 文科生还参加今年的春招吗 #
12955次浏览 98人参与
# 找工作中的小确幸 #
81424次浏览 451人参与
# 你的秋招第一场笔试是哪家 #
291676次浏览 2082人参与
# 实习越久越好,还是多多益善? #
77952次浏览 343人参与
# 找实习多的是你不知道的事 #
1805010次浏览 20688人参与
# 大家每天通勤多久? #
85918次浏览 812人参与
# 26届的你,投了哪些公司? #
256228次浏览 1685人参与
# 如何缓解入职前的焦虑 #
260945次浏览 1466人参与
# 记录实习开销 #
186980次浏览 947人参与
# 正在实习的你,几点下班 #
299397次浏览 2186人参与
