这题有人会吗
2025-07-10 20:42:14
发布于：江苏
36阅读
0回复
0点赞
盖亚正在军事学院进修，他需要上完所有的课程，才能获得战争学博士学位。
但是军事学院的课程之间有一定的依赖关系。比如你需要学习了离心机使用课程，才能学习核燃料制备课程。但是有传言说军事学院已经被间谍渗透，所有人都无法学完所有的课程。
现在盖亚已经拿到了所有的课程依赖关系，想知道他是否能学完所有的课程。
输入格式
第一行输入一个整数
n
(
1
≤
n
≤
100000
,
1
≤
m
≤
200000
)
n(1≤n≤100000,1≤m≤200000)，
n
n 为课程总数，
m
m 为依赖关系数量。
第
2
2 行到第
m
+
1
m+1 行每行输入2个整数
x
,
y
x,y 。表示需要先上课程
x
x 才能上课程
y
y。
输出格式
如果可以上完所有课程，输出“YES”，否则输出"NO"
求解
全部评论 4
这是代码
#include <iostream> #include <queue> #include <vector> using namespace std; constexpr int N = 2e5+1; vector<int> adj[N],in(N); void tope(const int n) { queue<int> q; for (int i = 1;i <= n;i++) { if (!in[i]) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); for (auto &v : adj[u]) { in[v]--; if (!in[v]) { q.push(v); } } } } int main() { int n,m; cin>>n>>m; adj[1].clear(); for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); in[v]++; } tope(n); for (int v = 1;v<=n;v++) { if (in[v]) { cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; return 0; }2025-08-06 来自 浙江
1
有帮助，赞一个