TJU : 1614 (Is It A Tree?)


// http://acm.tju.edu.cn/toj/showp1614.html

// @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 <utility>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

struct node {
    int name;
    bool haveChild;
    vector <int> inDegree;
} a [100000];

void reset ()
{
    for ( int i = 0; i < 100000; i++ ) {
        a [i].haveChild = false;
        a [i].inDegree.clear ();
    }
}


int main ()
{
    int f;
    int s;
    int cases = 0;

    while ( scanf ("%d %d", &f, &s) ) {
        if ( f < 0 && s < 0 )
            break;

        reset ();
        map <int, int> indexMapping;
        int length = 1;
        bool isTree = true;

        while ( f != 0 || s != 0 ) {

            if ( f == s )
                isTree = false;

            if ( !indexMapping [f] )
                indexMapping [f] = length++;

            a [indexMapping [f]].name = f;
            a [indexMapping [f]].haveChild = true;

            if ( !indexMapping [s] )
                indexMapping [s] = length++;

            a [indexMapping [s]].name = s;
            a [indexMapping [s]].inDegree.push_back (f);

            scanf ("%d %d", &f, &s);
        }

        int root = 0;

        for ( int i = 1; i < length; i++ ) {
            if ( a [i].inDegree.size () == 0 ) {
                root++;
                if ( !a [i].haveChild || root > 1 ) {
                    isTree = false;
                    break;
                }
            }
            else if ( a [i].inDegree.size () > 1 ) {
                isTree = false;
                break;
            }
        }

        if ( (isTree && root == 1) || length == 1 )
            printf ("Case %d is a tree.\n", ++cases);
        else
            printf ("Case %d is not a tree.\n", ++cases);
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

One thought on “TJU : 1614 (Is It A Tree?)

  1. Judge Data :
    Input : 
    6 8  5 3  5 2  6 4
    5 6  0 0
    
    8 1  7 3  6 2  8 9  7 5
    7 4  7 8  7 6  0 0
    
    3 8  6 8  6 4
    5 3  5 6  5 2  0 0
    
    0 0
    
    1 2
    1 3
    0 0
    
    1 2
    1 3
    1 4
    2 5
    2 6
    2 7
    3 8
    3 9
    3 10
    4 11
    4 12
    4 13
    0 0
    
    1 2
    0 0
    
    1 2
    1 3
    4 5
    0 0
    
    1 1
    0 0
    
    1 2
    2 1
    0 0
    
    1 2
    1 2
    0 0
    
    1 2
    1 3
    2 4
    2 5
    2 6
    2 7
    3 8
    8 9
    9 10
    10 11
    11 12
    12 13
    0 0
    
    -1 -1
    
    Judge Data :
    Output :
    Case 1 is a tree.
    Case 2 is a tree.
    Case 3 is not a tree.
    Case 4 is a tree.
    Case 5 is a tree.
    Case 6 is a tree.
    Case 7 is a tree.
    Case 8 is not a tree.
    Case 9 is not a tree.
    Case 10 is not a tree.
    Case 11 is not a tree.
    Case 12 is a tree.
    
    

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