首页 > 代码库 > 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 期末考试