HDU 5154 Harry and Magical Computer【トポロジーソート】

Harry and Magical Computer
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 73    Accepted Submission(s): 34
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   Source
BestCoder Round #25
还有,需要问一下魔法のコンピュータを利用してN個の任務を処理して、しかしM個の前後の関係(a,b)があって、
bが実行する前にaを実行しなければならないという意味です.つまり、aタスクはbタスクの前に、要求を満たすことができるかどうかを聞きます.
このN個の任務を処理した.
構想:トポロジーソート、キューを使用しました.まずすべての入度が0の点を入隊し、Countで統計します.
入度が0でない点.キュー内のポイントに接続されているすべてのエッジを巡回し、そのポイントがエッジの反対側に接続されていることを減らします.
入度は,他端が0であればキューに入れ,その一端の個数idを統計する.
最後にidとCountが等しいかどうかを比較すると,このN個のタスクを処理できるかどうかを判断できる.

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 110;
const int MAXM = 10010;

int head[MAXN],indegree[MAXM],N,M,T;
struct EdgeNode
{
    int to;
    int w;
    int next;
};
EdgeNode Edges[MAXM];


int toposort()
{
    queue<int> Q;
    int u;
    int Count = 0;
    for(int i = 1; i <= N; i++)
    {
        if(indegree[i] == 0)
            Q.push(i);
        else
            Count++;
    }
    int id = 0;
    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for(int i = head[u]; i != -1; i = Edges[i].next)
        {
            indegree[Edges[i].to]--;
            if(indegree[Edges[i].to]==0)
            {
                id++;
                Q.push(Edges[i].to);
            }
        }
    }
    if(id < Count)
        return false;
    else
        return true;
}
int main()
{
    int x,y;
    while(cin >> N >> M)
    {
        memset(head,-1,sizeof(head));
        memset(indegree,0,sizeof(indegree));
        for(int i = 0; i < M; i++)
        {
            cin >> x >> y;
            Edges[i].to = y;
            Edges[i].w = 1;
            Edges[i].next = head[x];
            head[x] = i;
            indegree[y]++;
        }
        if(toposort())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}