BC Harry and Magical Computer (拓扑排序)

Harry and Magical Computer

 

 Accepts: 350

 

 Submissions: 1348

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 32768/32768 K (Java/Others)

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




拓扑排序模板题。注意在处理IN[i] ++的时候要先判断是否已经存在这条边。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <cstdlib>
using    namespace    std;

const    int    SIZE = 105;
int    IN[SIZE];
bool    G[SIZE][SIZE];
int    N,M;

bool    toposort(void);
int    main(void)
{
    int    from,to;

    while(scanf("%d%d",&N,&M) != EOF)
    {
        fill(IN,IN + SIZE,0);
        fill(&G[0][0],&G[SIZE - 1][SIZE - 1],false);
        for(int i = 0;i < M;i ++)
        {
            scanf("%d%d",&from,&to);
            if(!G[from][to])
                IN[to] ++;
            G[from][to] = 1;
        }
        if(toposort())
            puts("YES");
        else
            puts("NO");
    }

    return    0;
}

bool    toposort(void)
{
    int    count = 0;
    queue<int>    que;

    for(int i = 1;i <= N;i ++)
        if(!IN[i])
            que.push(i);

    while(!que.empty())
    {
        int    cur = que.front();
        que.pop();
        count ++;

        for(int i = 1;i <= N;i ++)
            if(G[cur][i])
            {
                IN[i] --;
                if(!IN[i])
                    que.push(i);
            }
    }
    if(count < N)
        return    false;
    return    true;
}