华为机考试题：查找知识图谱中的实例知识_华为机试电影知识图谱和查询系统

        知识图谱是一种结构化的语义网络，用于描述物理世界中的概念及其实例的相关关系。可以把知识图谱看成是一种有向图，图中的点是概念或实例，图中的边是概念及其实例的相关关系。
现定义一种简单的知识图谱：
概念：包括父概念及其子概念，通过 subClasso关系关联，父子概念可以有多个层级；
实例：仅和概念之间通过 instanceOf关系关联；
关系：以三元组的形式表示，三元组是一个以空格为成员间分隔符的字符串。例如"student subClassof person"表示 student是person的子概念；apple instanceof fruit表示apple是fruit概念的实例。
给定一个知识图谱，请编写一个方法，可以根据一个概念查找其所有的实例。如果一个概念拥有子概念，那么返回的结果需要包含其所有子概念的实例；如果输入的概念没有实例，则返回字符串empty"(说明：输出字符串文本不需要包含引号)。
给定的图谱满足以下限制：
1、有向图中不存在环路；
2、所有点和关系的定义对大小写敏感；
解答要求
时间限制CC++1000ms，其他语言：2000ms
内存限制CC++32MB，其他语言：64MB
输入
输入第1行，表示图谱中关系的数量n，取值范围[1,10000]
从第2行到n+1行，表示图谱中的关系，每一行是一个关系三元组。
第n+2行，表示待查找的元节点,是关系三元组中存在的点。
每行字符的长度不超过100

输出
按字典序升序排列的字符串数组，其内容是概念及其子概念的所有实例。

注释：什么是字典序？在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

样例1
输入：3
 student subClassOf person
 Tom instanceOf student
 Marry instanceOf person
 person
输出：Marry Tom
解释：studentperson是的子概念，Tom是 student的实例，Marryperson是的实例，Marry的字典序小于Tom，所以返回 Marry Tom
样例2
输入：1
 apple instanceOf fruit
 fruit
输出：apple
解释：applefruit是的唯一实例，所以返回 apple

# -*- coding: utf-8 -*-
 
n = int(input("图谱关系数n："))
 
keyWords = ['subClassOf','instanceOf']
class_dict = {}
instance_dict = {}
 
for i in range(n):
    relation = input('关系三元组' + str(i) + '：')
    relation_list = relation.split(' ') #关系拆分
    son = relation_list[0]
    key = relation_list[1]
    parent = relation_list[2]
    
    if key == 'subClassOf': #这是子概念 
        class_dict[i] = dict([(parent,son)])
    elif key == 'instanceOf': #这是一个实例 
        instance_dict[i] = dict([(parent,son)])
    else: #关键词错误
        print('关键词错误！')
        break
 
def f(dir_dict,key):
    result = []
    for tmp in dir_dict.keys(): #遍历实例字典
        temp = dir_dict[tmp]
        for tmp in temp.keys(): #查实例字典，找出实例
            #遍历的所有实例字典中有多少个该子类的实例，存在instance中
            if key == tmp:
                result.append(temp[key])            
    return result #有可能为空，需要校验
 
node = input("待查询的概念：")
son = [node]
instance = []
for i in range(n): #遍历所有类字典，最多n轮，只可能更少
    temp = f(class_dict,node) #所有的子类
    if temp != []: #有子类，那么继续查这个子类还有没有子类，son返回所有该节点的子类    
        son.append(temp[0])   
        node = temp[0]
    else:
        break #无子类就退出
        
if son == []: # 无子类
    instance = f(instance_dict,node) #没有子类，查有没有实例 
    if instance != []:
        print('无子类，只有一个实例：',instance)
    else:
        print('既无子类，也无实例！')
else: # 有子类
    for tmp in son: #遍历所有字典
        instance.append(f(instance_dict,tmp)[0])
    if instance != []:
        instance.sort() #排序
        for tmp in instance:
            print(tmp,end=" ")
    else:
        print('empty')
        print('有子类，无实例！')