HDU 5154 Harry and Magical Computer 拓撲排序

水題不解釋

拓撲排序判斷有無環

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 \leq n \leq 100, 1 \leq m \leq 10000$
The next following m lines, each line contains two numbers a b, indicates a dependencies (a, b). $1 \leq a, b \leq 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 

#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct node
{
    int u,v,next;
} edge[1100000];
int head[1000000],vis[200000],rudu[200000],cnt,n;
void add(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void topu()
{
    memset(vis,0,sizeof(vis));
    int s=0;
    queueq;
    while(!q.empty())
        q.pop();
    for(int i=1; i<=n; i++)
    {
        if(rudu[i]==0)
        {
            q.push(i);
            vis[i]=1;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        s++;
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            if(rudu[edge[i].v])
            {
                rudu[edge[i].v]--;
            }
            if(rudu[edge[i].v]==0&&vis[edge[i].v]==0)
            {
                q.push(edge[i].v);
                vis[edge[i].v]=1;
            }
        }
    }
    if(s==n)
        printf("YES\n");
    else
        printf("NO\n");
}
int main()
{
    int m;
    while(~scanf("%d %d",&n,&m))
    {
        cnt=0;
        memset(rudu,0,sizeof(rudu));
        memset(head,-1,sizeof(head));
        for(int i=0; i