时间限制: 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 10010 using namespace std;
int n,m,num,head[maxn],du[maxn],tot;
queue<int>q;
struct node
{
int v,pre;
}e[maxn*];
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=;i<=m;i++)
{
scanf("%d%d",&x,&y);
Add(x,y);
du[y]++;
}
for(int i=;i<=n;i++)
{
if(du[i]==)
{
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>=) printf("pass");
else printf("I'll die!");
return ;
}