hdoj5154

题目：

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

根据题目意思，可以知道此题为拓扑排序。
此题会出现一种情况：环。因为拓扑排序要求此图是有向无环图，因此如果有环，肯定不能拓扑排序（输出NO），如果能用拓扑排序，则输出YES.

由于拓扑排序每次都找到入度为0的点，然后入队列维护。如果此有向图有环，必然存在入度无法减为0的点，因此可以统计最终出队列的个数是否为n.

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int MAVE = 10000+10;
const int MAXV = 100+10;
using namespace std;
struct edge {
    int next,to;
} e[MAVE];
int head[MAXV],tot;
void init() {
    memset(head,-1,sizeof(head));
    tot = 0;
}
void add_edge(int a,int b) {
    e[tot].next = head[a];
    e[tot].to = b;
    head[a] = tot++;
}
int n,m;
int din[MAXV];
bool topo() {
    queue<int> que;
    for (int i = 1;i <= n;++i) {
        if (din[i] == 0) que.push(i);
    }
    int cnt = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u];i != -1;i = e[i].next) {
            int v = e[i].to;
            --din[v];
            if (din[v] == 0) {
                que.push(v);
            }
        }
        cnt++;
    }
    if (cnt == n) {
        return true;
    }
    else return false;
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        memset(din,0,sizeof(din));
        int a,b;
        for (int i = 1;i <= m;++i) {
            scanf("%d%d", &a, &b);
            add_edge(a,b);
            din[b]++;
        }
        if (topo()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}