HDU : Legal or Not


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;


int main ()
{
    int numbers;
    int relation;

    while ( scanf ("%d %d", &numbers, &relation) ) {

        vector <int> matrix [100 + 5];
        int inDegree [100 + 5];

        memset (inDegree, 0, 105 * sizeof (int));

        if ( numbers == 0 && relation == 0 )
            break;

        for ( int i = 0; i < relation; i++ ) {
            int a, b;
            scanf ("%d %d", &a, &b);
            matrix [a].push_back (b);
            inDegree [b]++;
        }

        queue <int> Q;

        for ( int i = 0; i < numbers; i++ ) {
            if ( inDegree [i] == 0 )
                Q.push (i);
        }

        while ( !Q.empty () ) {
            int pop = Q.front ();
            Q.pop ();

            for ( unsigned int i = 0; i < matrix [pop].size (); i++ ) {
                inDegree [matrix [pop] [i]]--;
                if ( inDegree [matrix [pop] [i]] == 0 )
                    Q.push (matrix [pop] [i]);
            }
        }

        int countInDegree = 0;

        for ( int i = 0; i < numbers; i++ ) {
            countInDegree += inDegree [i];
        }

        if ( countInDegree == 0 )
            printf ("YES\n");
        else
            printf ("NO\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s