例题：hdu 5154 链接 http://acm.hdu.edu.cn/showproblem.php?pid=5154
题目意思是第一行先给出n和m表示有n件事，m个关系，接下来输入m行，每行有a，b两个数，他们之间的关系就是第a件事要在
第b件事之前做完，然后问你可不可以在符合这m个关系的情况下把这n件事情做完，可以就输出YES，否则输出NO。
现在先假设a b之间的关系用a指向b来表示，即a-->b。
题目里给的两个样例有点简单，来个稍微复杂一点的好吧。
第一次搞这个，不太会，见谅。看上面这个图，然后我们可以先得到这些数据：
6 7
1 5
1 3
2 5
3 4
3 5
3 6
5 6
入度：就理解为一个点被箭头指的次数（作为终点的次数），上图中 点1的入度为0，点5的入度为3，点3的入度为1。
出度：反一下，箭头出去的次数（作为起点的次数），点1的出度为2，点5的为1。（出度在这题用不到）
我们程序就是先找到入度为0（一开始有点1和点2）的点，然后把这个点标记为走过，再把以这个点为起点的边删掉，
我们先选点1，然后就下面酱紫了。
然后入度为0的点就有点2和点3了，随便选择一个，假设3好吧，然后：
一直这样下去
然后就没有然后了，把点4删了就完了。
以上是符合条件输出YES的情况，假设图是这样的
那么1和3就构成了一个环，入度为0的点只有2，然后删去2和以2位起点的边：
然后就没有入度为0的边了，然后程序结束，可是所有的点还没有走完（没有做完所有的事情），输出NO。
接下来就是怎么写的问题了。看代码吧
用vector的：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int>v[];
int n,m,k,t;
int num[],vis[];//num数组记录入度数目，vis数组看这个点是否访问过
void init()
{
for(int i=;i<=n;i++)
v[i].clear();
memset(num,,sizeof(num));
memset(vis,,sizeof(vis));
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
num[b]++; //点b入度 +1
v[a].push_back(b);//a-->b
}
int flag=;
for(int i=;i<=n;i++)//最多n次循环
{
for(int j=;j<=n;j++)//找1到n入度为0的点
{
if(vis[j])
continue;
if(num[j]==)
{
vis[j]=;//标记这个点走过
for(int k=;k<v[j].size();k++)
{
if(num[v[j][k]])
num[v[j][k]]--;//删边
}
}
}
}
for(int i=;i<=n;i++)
{
if(!vis[i])//看是不是所有事都做完了
flag=;
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return ;
}
再用队列和链式前向星优化一下：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,t;
struct node{
int v,next;
}str[];
int head[],vis[],in[],cnt;
queue<int>q;
void add(int u,int v)
{
str[++cnt].v=v;
str[cnt].next=head[u];
head[u]=cnt;
}
void init()
{
memset(vis,,sizeof(vis));
memset(head,-,sizeof(head));
memset(in,,sizeof(in));
cnt=;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
in[b]++;
}
while(!q.empty())
q.pop();
for(int i=;i<=n;i++)
{
if(!in[i])
q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
for(int i=head[u];i!=-;i=str[i].next)
{
int v=str[i].v;
if(in[v])
in[v]--;
if(in[v]==&&!vis[v])
q.push(v);
}
}
int flag=;
for(int i=;i<=n;i++)
{
if(!vis[i])
{
flag=;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return ;
}