首页 > 代码库 > codevs 2915 期末考试
codevs 2915 期末考试
时间限制: 1 s
空间限制: 16000 KB
题目等级 : 黄金 Gold
题目描述 Description
期末考试要来了,某同学正在努力复习。
他要复习N个知识点,每个知识点需要一定的知识做基础。
现给你一个AOV网,其中有M条边<Ai,Bi>。
问他能考得怎样?(假设他只要复习了就不会出错,没复习就什么也不会)
输入描述 Input Description
两个正整数N,M
M行,Ai Bi。
输出描述 Output Description
若能考满分,输出Oh,yeah!
若能及格(不是满分),输出pass
若不及格,输出I‘ll die!
样例输入 Sample Input
5 4
1 4
4 5
2 3
3 2
样例输出 Sample Output
pass
数据范围及提示 Data Size & Hint
对于1个点,N=1,M=0。
全部点N<=10.
可能有自环。
拓扑排序
屠龙宝刀点击就送
#include <iostream>#include <cstring>#include <cstdio>#include <queue>#define maxn 10010using namespace std;int n,m,num,head[maxn],du[maxn],tot;queue<int>q;struct node{ int v,pre;}e[maxn*3];void Add(int from,int to){ num++; e[num].v=to; e[num].pre=head[from]; head[from]=num;}int main(){ scanf("%d%d",&n,&m); int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); Add(x,y); du[y]++; } for(int i=1;i<=n;i++) { if(du[i]==0) { q.push(i); tot++; } } while(!q.empty()) { int k=q.front(); q.pop(); for(int i=head[k];i;i=e[i].pre) { int v=e[i].v; du[v]--; if(!du[v]) { q.push(v); tot++; } } } if(tot==n) printf("Oh,yeah!"); else if(tot<=n&&tot>=1) printf("pass"); else printf("I‘ll die!"); return 0;}
codevs 2915 期末考试
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。