-
题目描述：
-
如果A，B是C的父母亲，则A，B是C的parent，C是A，B的child，如果A，B是C的（外）祖父，祖母，则A，B是C的grandparent，C是A，B的grandchild，如果A，B是C的（外）曾祖父，曾祖母，则A，B是C的great-grandparent，C是A，B的great-grandchild，之后再多一辈，则在关系上加一个great-。
-
输入：
-
输入包含多组测试用例,每组用例首先包含2个整数n（0<=n<=26）和m（0
当n和m为0时结束输入。
-
输出：
-
如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。
具体含义和输出格式参见样例.
-
样例输入：
-
3 2
ABC
CDE
EFG
FA
BE
0 0
这个题目第一眼看上去很像并查集，但是仔细分析可以发现，这个题目是利用已知条件构造森林然后对其中的关系进行查找。
题目的第一行的两个输入分别是所有的information的个数，第二个输入是所有的quest的个数。
接下来的几行是information，以ABC为例，B为A的parent，C为A的parent。根据这个关系，我们可以想到建立树的方法：利用一维的数组存储，然后数组中存放数组下标对应的子孙所在位置。那么可以想到用stl中的map容器进行处理。
把森林（树）构造完毕后，我们对所有的quest进行查询。很自然就是顺着child这个内容进行查找。下面函数的find就是实现这个功能。
PS:有一种很简单的检测程序对错的测试办法，记着二叉树了没？
#include
#include
<script type="text/java script">
-
<script type="text/java script">BAIDU_CLB_fillSlot("771048");
-
点击复制链接 与好友分享!
回本站首页
<script>
function copyToClipBoard(){
var clipBoardContent=document.title + '\r\n' + document.location;
clipBoardContent+='\r\n';
window.clipboardData.setData("Text",clipBoardContent);
alert("恭喜您！复制成功");
}
<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
-
您对本文章有什么意见或着疑问吗？请到
论坛讨论您的关注和建议是我们前行的参考和动力??
-
上一篇：
Codeforces Round #294 (Div. 2) -- C. A and B and Team Training
-
下一篇：
Codeforces Round #294 (Div. 2) -- B. A and B and Compilation Errors
-
相关文章
-
<script type="text/java script">BAIDU_CLB_fillSlot("182716");
-
<script type="text/java script">BAIDU_CLB_fillSlot("517916");
-
图文推荐
<script>
(function(){
var appid = 'cyrBEfE7C',
conf = 'prod_830794cf494da8b808afb2994cfe0fee';
var doc = document,
s = doc.createElement('script'),
|
