HDU 5154 Harry and Magical Computer（拓扑排序模板）

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.

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

题意：有n个任务需要全部完成，但是现在有m个条件，必须在满足这m个条件的同时完成n个任务，这m个条件中每组的两个任务（a，b），任务b必须在任务a完成之前完成，问能否完成所有的任务。

拓扑排序（并输出该序列）：1.从有向图中找一个没有前趋的结点v（入度为0），若v不存在，则表明不可进行拓扑排序（有环路），结束；

2.输出v；

3.将v从图中删除，同时删除与v有关的所有边；

4.若图中所有点均已输出，则结束（成功排序），否则转1继续进行。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int N=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;

typedef long long LL;

struct node
{
    int v, next;
}no[N];
int Head[N], ru[N], vis[N], k;

void Init()
{
    memset(Head, -1, sizeof(Head));
    memset(ru, 0, sizeof(ru)); ///记录每个结点的入度个数
    memset(vis, 0, sizeof(vis)); ///标记该点是否被查找

    k = 0;
}

void Add(int a, int b)
{
    no[k].v = b;
    no[k].next = Head[a];

    Head[a] = k++;
}

int main ()
{
    int n, m, flag, i, num, Min, v, a, b;

    while (scanf("%d%d", &n, &m) != EOF)
    {
        Init();
        num = 0;
        flag = 1;

        while (m--)
        {
            scanf("%d%d", &a, &b);

            ru[a]++;
            Add(b, a);
        }

        while (num < n)
        {
            Min = INF;

            for (i = 1; i <= n; i++)
            {
                if (!ru[i] && i < Min && !vis[i]) ///查找入度为0的最小结点
                    Min = i;
            }

            if (Min == INF) ///没有查找到入度为0的结点，排序失败，结束
            {
                flag = 0;
                break;
            }

            vis[Min] = 1; ///将查找过的入度为0的点标记（即在图中删除该点）

            for (i = Head[Min]; i != -1; i = no[i].next)
            {
                v = no[i].v;
                ru[v]--; ///与之相连的边也需要删除
            }

            num++; ///num记录成功结点的个数
        }

        if (flag == 1) printf("YES
");
        else printf("NO
");
    }

    return 0;
}