4 - 09. 피리칼 나무(25)

4 - 09. 피리칼 나무 (25) 제목 주소
시간제한 400ms 메모리 제한 65536kB 코드 길이 제한 8000B 판정 프로그램 Standard 피리칼 트리는 특수한 두 갈래 나무로 그 결점은 두 개의 키워드 K1과 K2를 포함한다.우선 피리칼 나무는 K1에 대한 두 갈래 검색 트리입니다. 즉, 결점 왼쪽 나무의 모든 K1 값은 이 결점의 K1 값보다 작고 오른쪽 나무는 큽니다.그 다음으로 모든 결점의 K2 키워드는 우선 대기열(최소 더미로 설정해도 무방하다)의 순서 요구를 충족시킨다. 즉, 이 결점의 K2 값은 하위 트리의 모든 결점의 K2 값보다 작다.두 갈래 나무 한 그루를 정하고 피리칼 나무 여부를 판단하세요.
형식 설명을 입력합니다.
먼저 정수 N(<=1000)을 입력하여 트리의 결점 개수를 지정합니다.그 다음에 N줄은 매 줄마다 결점에 대한 정보를 제공한다. 결점의 K1값, K2값, 왼쪽 아이의 결점 번호, 오른쪽 아이의 결점 번호를 포함한다.0~(N-1) 순서로 끝점을 지정합니다.만약 어떤 결점에 아이의 결점이 존재하지 않는다면 이 위치는 -1이다.
출력 형식 설명:
YES를 출력합니다. 이 나무가 피리칼 나무라면;그렇지 않으면 출력이 NO입니다.
샘플 입력 및 출력:
번호 입력 출력 1 6 8 27 5 1 9 40 -1 10 20 3 12 21 -1 4 15 22 -1 5 35 -1 YES 2 6 8 27 5 1 9 40 -1 10 20 3 12 11 -1 15 22 -1 50 35 -1 -1 10 20 3 12 22 -1 14 15 21 6 -1 15 35 -1 13 23 -1 -1 1 NO 4 6 8 27 5 1 9 40 -1 10 20 3 12 -1 14 22 -1 5 35 -1 35 -1 NO 5 9 11 5 3 -1 15 3 4 7 5 2 6 6 8 -1 8-1 9 6 -1 8 10 1 2 1 2 4 -1 -1 20 7 -1 -1 12 9 -1 -1 NO 6 1 1 1 -1 -1 YES

사용하고 수집하여 두 갈래 나무를 만들고 두 갈래 나무의 뿌리를 훑어보며 대기열queue<>로 작은 나무를 판단한다

40분 안에 완성할 수 있도록 자주 두드려야 한다

/* 4 - 09.  （25） http://www.patest.cn/contests/ds/4-09 */
#include <iostream> 
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

#define N 1001

int n;

struct mydata{
    int k1;
    int k2;
    int left;
    int right;
    mydata(int _k1=0, int _k2=0, int _left=-1, int _right=-1) :k1(_k1), k2(_k2), left(_left), right(_right){}
};

typedef struct node{
    int k1, k2;
    struct node* left;
    struct node* right;
    node(int _k1 = 0, int _k2 = 0) :k1(_k1), k2(_k2), left(NULL), right(NULL){}
}BNode;

int father[N];
mydata datas[N];

int find(int x)
{
    if (x == father[x])
        return x;
    return father[x] = find(father[x]);
}

void merg(int x, int y) //  
{
    father[find(y)] = find(x);
}

BNode* root;

BNode* createTreeK1(BNode* root, int i)
{
    if (root == NULL)
    {
        root = new node(datas[i].k1,datas[i].k2);
        if (datas[i].left != -1)
        {
            root->left = createTreeK1(root->left, datas[i].left);
        }
        if (datas[i].right != -1)
        {
            root->right = createTreeK1(root->right, datas[i].right);
        }
    }
    return root;
}

//  
vector<int> vin;
void inorder(BNode* root)
{
    if (root != NULL)
    {
        inorder(root->left);
        vin.push_back(root->k1);
        inorder(root->right);
    }
}

bool isXiaodui(BNode* root) //  
{
    queue<BNode*> que;
    while (!que.empty())
    {
        que.pop();
    }
    que.push(root);
    while (!que.empty())
    {
        BNode* rt = que.front();
        que.pop();

        int data = rt->k2;
        if (rt->left != NULL)
        {
            if (rt->left->k2 <= data)
                return false;
            que.push(rt->left);
        }
        if (rt->right != NULL)
        {
            if (rt->right->k2 <= data)
                return false;
            que.push(rt->right);
        }
    }
    return true;
}

int main()
{
    //freopen("in", "r", stdin);
    while (scanf("%d", &n) != EOF)
    {
        int i;
        for (i = 0; i < n; i++)
        {
            father[i] = i;
        }
        for (i = 0; i < n; i++)
        {
            scanf("%d%d%d%d", &datas[i].k1, &datas[i].k2, &datas[i].left, &datas[i].right);
            if (datas[i].left != -1)
            {
                if (find(i) != find(datas[i].left))
                    merg(i, datas[i].left);
            }
            if (datas[i].right != -1)
            {
                if (find(i) != find(datas[i].right))
                    merg(i, datas[i].right);
            }
        }

        int rootNum = find(0);
        root = NULL;
        root = createTreeK1(root, rootNum);

        vin.clear();
        inorder(root);
        bool flag1 = true;
        for (i = 1; i < n; i++)
        {
            if (vin[i] <= vin[i - 1]) //      
            {
                flag1 = false;
                break;
            }
        }
        if (flag1)
        {
            bool flag2 = isXiaodui(root);
            if (flag2)
            {
                printf("YES");
            }
            else{
                printf("NO");
            }
        }
        else{
            printf("NO");
        }
        printf("
");
    }
    return 0;
}