HDU 5154 拓扑排序

题面：

Harry and Magical Computer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2183    Accepted Submission(s): 862


Problem Description In reward of being yearly outstanding magic student, Harry gets a magical computer. When the computer begins to deal with a process, it will work until the ending of the processes. One day the computer got n processes to deal with. We number the processes from 1 to n. However there are some dependencies between some processes. When there exists a dependencies (a, b), it means process b must be finished before process a. By knowing all the m dependencies, Harry wants to know if the computer can finish all the n processes.  
Input There are several test cases, you should process to the end of file.
For each test case, there are two numbers n m on the first line, indicates the number processes and the number of dependencies. 1≤n≤100,1≤m≤10000
The next following m lines, each line contains two numbers a b, indicates a dependencies (a, b). 1≤a,b≤n  
Output Output one line for each test case.
If the computer can finish all the process print "YES" (Without quotes).
Else print "NO" (Without quotes).  
Sample Input

3 2 3 1 2 1 3 3 3 2 2 1 1 3  
Sample Output

YES NO

题意：

     任务之间有依赖关系，如a->b，那么必须先完成任务b，才能完成任务a，问是否能够完成全部任务。

解题：

    经典的拓扑排序，找入度为0的点，不断入队列，广搜即可，最后看是否所有点都被访问了。

代码：

#include#include#include#include#define inf 1000000
using namespace std;
struct edge
{
    int fm,to,nxt;
}store[10010];
int in[105],vis[105],head[105],n,cnt;
void addedge(int a,int b)
{
    store[cnt].nxt=head[a];
    head[a]=cnt;
    store[cnt].fm=a;
    store[cnt++].to=b;
}
queueq;
void bfs()
{
   int cur;
   for(int i=1;i<=n;i++)
       if(in[i]==0)
           q.push(i);
   while(!q.empty())
   {
       cur=q.front();
       q.pop();
       vis[cur]=1;
       for(int i=head[cur];~i;i=store[i].nxt)
       {
           int v=store[i].to;
           in[v]--;
           if(in[v]==0)
               q.push(v);
       }
   }
}
int main()
{
    int m,a,b;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            addedge(b,a);
            in[a]++;
        }
        bfs();
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                flag=0;
                break;
            }
        }
        if(flag)
            printf("YESn");
        else
            printf("NOn");
    }
    return 0;
}