首页 > 试题广场 >

找出直系亲属

[编程题]找出直系亲属
  • 热度指数：9254 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    如果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<m<50）, 分别表示有n个亲属关系和m个问题, 然后接下来是n行的形式如ABC的字符串，表示A的父母亲分别是B和C，如果A的父母亲信息不全，则用-代替，例如A-C,再然后是m行形式如FA的字符串,表示询问F和A的关系。
   


输出描述:
    如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。
    具体含义和输出格式参见样例.
示例1

输入

3 2
ABC
CDE
EFG
FA
BE

输出

great-grandparent
-
算法知识视频讲解
开通博客
头像 limitcc
发表于 2022-02-03 11:00:02
采用并查集思想，用son数组记录自己儿子结点，用height数组记录高度作为辈分 运行时间：3ms超过66.87% 用C++提交的代码 占用内存：404KB超过81.96%用C++提交的代码 #include <iostream> #include <string> 展开全文
去ta的博客 赞 (11) 回复(2) 收起
头像 健康快乐最重要
发表于 2020-04-07 21:19:54
本来要用并查集的，发现并查集只能解决‘-’还是非‘-’的问题。干脆直接用dfs搜索一下（这个图非常小 26*26的图）。如果from到to搜不通，就从to到from再搜一次。 #include<iostream> #include<string> #include<v 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 夏倾尘
发表于 2021-02-06 10:56:10
其实本质相当于倒过来的二叉树 比如题目中的例子 A是BC的孩子，那么应该建立由B向A的链表和由C向A的链表，这样的目的是从任何一个节点向下遍历方向是唯一的，容易确定先后顺序 比如我想知道G和C是不是直系亲属，那么从G遍历下来的路径是GECA，这里面包含了C，所以G是C的爷爷（因为隔了两代） 如果判断 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 程昱同学
发表于 2023-01-26 17:51:07
#include <bits/stdc++.h> using namespace std; int relations_num, questions_num; int child, mom, papa; char c, m, p; char pp1, pp2; int p1, p2; i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 愿offer多多的外卷侠很自信
发表于 2022-09-12 14:41:10
#include<cstdio> #include<iostream> #include<utility> #include<map> // 采用并查集思想，用son数组记录自己儿子结点 using namespace  展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 2030ssxx
发表于 2024-09-18 19:40:12
/* 人还挺无语的，就这也叫困难题，难度划分一点也不靠谱。这道题甚至一点难的算法思想和复杂数据结构都没用到 一开始脑瓜子嗡嗡的，不知道怎么下手，看了部分题解，感觉有的人的方法非常清晰易懂就选用了 首先这题最小的儿子作为根节点，辈份越大，高度越低，深度越小 按照输入记录每个结点的儿子和深度 然 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sjtuer02
发表于 2025-02-18 13:36:49
#include<iostream> #include<stdio.h> #include<vector> #include<map> using namespace std; vector<vector<char> >tree 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Coming680
发表于 2022-02-11 11:47:32
#include<iostream> #include<map> using namespace std; typedef map<char, pair<char, char>> MyMap; bool answer = false; int ccnt 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 辣_牛肉汤
发表于 2025-02-25 10:55:34
#include <iostream> #include<vector> using namespace std; bool ok; int direct(int x, int y, vector<int> v1) {//是否为直系亲属（ok），返回两者的相对层次 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 cheer98
发表于 2024-04-26 15:30:42
auther cheer 注意，此题的解法基础建立在“二孩政策”尚未实施之前，即一个parent最多仅有1个child。 如此，可将父母与孩子的关系看做一棵倒置的树。 输入：采用并查集union操作，son数组记录parent对应的son。初始化每个字母的son为其自身。 判断关系：首先通过递归 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

链表 树 并查集
难度：
86条回答 11776浏览

热门推荐

通过挑战的用户

查看代码

相关试题

找出直系亲属

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号