NOJ1554.cpp

//
//  main.cpp
//  lordofminecraft
//
//  Created by XadillaX on 14-4-28.
//  Copyright (c) 2014å¹´ XadillaX. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <list>
#include <map>
using namespace std;

#define MAXN (10000 + 5)

struct node
{
    node* parent;
    list<node*> children;
    
    int level;
    int begin, end;
};

node _node[MAXN];
int _node_index = 0;
node* new_node()
{
    node* nd = &_node[_node_index++];
    nd->parent = NULL;
    nd->children.clear();
    nd->level = 0;
    nd->begin = nd->end = 0;
    
    return nd;
}
void init_cache()
{
    _node_index = 0;
}

int cnt = 0;
map<string, node*> mp;

void make_tree_pair(char* name1, char* name2)
{
    node* nd1;
    node* nd2;
    nd1 = mp[name1];
    nd2 = mp[name2];
    
    if(nd1 == NULL)
    {
        nd1 = mp[name1] = new_node();
    }
    if(nd2 == NULL)
    {
        nd2 = mp[name2] = new_node();
    }
    
    nd1->parent = nd2;
    nd2->children.push_back(nd1);
}

void dfs(node* p, int level)
{
    p->level = level;
    p->begin = cnt++;
    
    for(list<node*>::iterator it = p->children.begin(); it != p->children.end(); it++)
    {
        dfs(*(it), level + 1);
    }
    
    p->end = cnt++;
}

int main()
{
    int n, q;
    
    while(~scanf("%d%d", &n, &q))
    {
        init_cache();
        mp.clear();
        
        int ans = 0;
        
        node* tmp = new_node();
        mp["Hungar"] = tmp;
        
        char name[2][15];
        for(int i = 0; i < n; i++)
        {
            scanf("%s%s", name[0], name[1]);
            make_tree_pair(name[0], name[1]);
        }
        
        dfs(tmp, 0);
        
        for(int i = 0; i < q; i++)
        {
            scanf("%s%s", name[0], name[1]);
            node* nd1 = mp[name[0]];
            node* nd2 = mp[name[1]];
            
            if(nd2->level < nd1->level)
            {
                printf("NO\n");
                //continue;
            }
            else
            if(nd2->level == nd1->level)
            {
                ans++;
                //printf("YES\n");
            }
            else
            {
                //printf("%d %d\n%d %d\n", nd1->begin, nd1->end, nd2->begin, nd2->end);
                if(nd1->begin < nd2->begin && nd1->end > nd2->end)
                {
                    //printf("NO\n");
                    continue;
                }
                else
                {
                    //printf("YES\n");
                    ans++;
                }
            }
        }
        
        printf("%d\n", ans);
    }

    return 0;
}