Harry and Magical Computer

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

3 2
3 1
2 1
3 3
3 2
2 1
1 3

YES
NO

 注意到：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.这一句，就是说b一定要在a前面完成，有一种先后关系，很明显拓扑。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int M = 105;

struct node{
    int to, next;
}e[M*M];
bool vis[M];
int in[M], head[M*M];
int n, m, tot;

void init(){
    /*for(int i = 0; i < M; ++ i){
        /map[i].clear();
        in[i] = 0;
        vis[i] = 0;
    }*/
    memset(in, 0, sizeof(in));
    memset(head, -1, sizeof(head));
}

void add(int a, int b){
    e[tot].to = a;
    e[tot].next = head[b];
    head[b] = tot++;
}

bool topo(){
    memset(vis, 0, sizeof(vis));
    int cou = 0, num;
    queue<int >q;
    for(int i = 1; i <= n; ++i)
        if(!in[i]){
            vis[i] = 1;q.push(i);
        }
    while(!q.empty()){
        int temp = q.front(); q.pop(); ++cou;
        for(int i = head[temp]; ~i; i = e[i].next){
            int v = e[i].to;
            if(!(--in[v])&&!vis[v]){
                q.push(v);
                vis[v] = 1;
            }
        }
    }
    if(cou == n) return 1;
    else return 0;
}

int main(){
    while(scanf("%d%d", &n, &m) == 2){
        init();
        int a, b;
        tot = 0;
        for(int i = 0; i < m; ++ i){
            scanf("%d%d", &a, &b);
            add(a, b); ++in[a];
        }
        //cout << "sad"<<endl;
        bool flag = topo();
        if(flag) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Hdoj 5154 Harry and Magical Computer 【拓扑】

原文：http://blog.csdn.net/shengweisong/article/details/44539295