Skip to content

1339: 继承图谱Detector

题目

题目描述

在继承图谱中,环形继承、棱形继承都会引发一些问题。

环形继承可能会导致IDE陷入无限的递归使内存资源消耗尽。

棱形继承则会使一个派生类含有多个底层的基类,常常需要使用虚继承(Virtual inheritance)的机制来避免。

需要你编写程序来检测是否发生了环形继承或棱形继承。

为了简化字符串操作,本题中的输入规则与c++的类声明有很大的不同,但继承逻辑是遵循c++的继承逻辑的。

本题中,类的声明部分如下:

类名 占一行,不超过30个字符 整数 k0 表示有k0个基类 接下来k0行,每行是 `继承方式(public,private,protected) 基类名` 来表示一个继承关系

本题中,不用考虑类声明顺序的影响。

输入格式

第一行是整数T,代表有T组测试数据

每组测试数据首先是正整数n。

接下来一行是n个类名称,表示接下来要被声明的类。

接下来是n个类的声明,声明的规则见上,声明的顺序对应上述类名出现的顺序。

输出格式

对于每组测试数据:

如果该继承图谱中含有环形继承,则输出Loop!,否则输出None,占一行。

如果该继承图谱中含有棱形继承,则输出Diamond!,否则输出None,占一行。

数据范围

样例输入

Sample 1

2 4 Alice Bob Calvin Diana Alice 1 public Diana Bob 1 protected Alice Calvin 1 public Bob Diana 1 private Calvin 4 Animal Cat Dog Catdog Animal 0 Cat 1 protected Animal Dog 1 protected Animal Catdog 2 public Cat public Dog

Sample 2

1 4 Alice Bob Calvin Diana Alice 2 public Diana protected Calvin Bob 1 protected Alice Calvin 1 public Bob Diana 1 private Calvin

样例输出

Sample 1

Loop! None None Diamond!

Sample 2

Loop! Diamond!

数据范围

1<=T<=10

1<=n<=10000

1<=m<=50000

m为继承的关系总数

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!