 dfs深搜)
L2-016 愿天下有情人都是失散多年的兄妹 (25分)呵呵。大家都知道五服以内不得通婚即两个人最近的共同祖先如果在五代以内即本人、父母、祖父母、曾祖父母、高祖父母则不可通婚。本题就请你帮助一对有情人判断一下他们究竟是否可以成婚输入格式输入第一行给出一个正整数N2 ≤ N ≤104 随后N行每行按以下格式给出一个人的信息本人ID 性别 父亲ID 母亲ID其中ID是5位数字每人不同性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考则相应的ID位置上标记为-1。接下来给出一个正整数K随后K行每行给出一对有情人的ID其间以空格分隔。注意题目保证两个人是同辈每人只有一个性别并且血缘关系网中没有乱伦或隔辈成婚的情况。输出格式对每一对有情人判断他们的关系是否可以通婚如果两人是同性输出Never Mind如果是异性并且关系出了五服输出Yes如果异性关系未出五服输出No。输入样例2400001M01111-100002F022220333300003M022220333300004F044440333300005M044440555500006F044440555500007F066660777700008M066660777700009M000010000200010M000030000600011F000050000700012F000080888800013F000090001100014M000100999900015M000100999900016M100000001200017F-10001200018F110000001300019F111000001800020F000151111000021M111000002000022M00016-100023M100120001700024M00022100139000210002400019000240001100012000220001800001000040001300016000170001500019000210001000011输出样例Never Mind Yes Never Mind No Yes No Yes No No本题思路本题也是一道dfs的衍生题目只不过需要分别对男方和女方分别进行dfs事先设置标志位如果重叠则说明有近亲来源输出No否则“Yes”。#includeiostream#includecstring#includealgorithm#includevectorconstintN100005;using namespace std;intn,k,aid,bid;intflag;vectorintvec[N];//存储关系树intvis[N];//标记关系数组charsex[N];//标记性别intid,fid,mid;//本身id, 父亲id, 母亲idvoiddfs(intx,intnum){vis[x]1;if(num4)return;for(inti0;ivec[x].size();i){if(!vis[vec[x][i]]){dfs(vec[x][i],num1);}else{flag1;}}}intmain(){cinn;while(n--){cinid;getchar();sex[id]getchar();cinfidmid;if(fid!-1){sex[fid]M;vec[id].push_back(fid);}if(mid!-1){sex[mid]F;vec[id].push_back(mid);}}cink;while(k--){cinaidbid;if(sex[aid]sex[bid]){coutNever Mindendl;continue;}flag0;memset(vis,0,sizeof(vis));dfs(aid,0);dfs(bid,0);if(flag1){coutNoendl;}else{coutYesendl;}}return0;} 
长河君 · 2026/10/27 9:22:52 · 阅读 1.2k 团体程序设计天梯赛-练习集 L2-016 愿天下有情人都是失散多年的兄妹 (25分) dfs深搜
L2-016 愿天下有情人都是失散多年的兄妹 (25分)呵呵。大家都知道五服以内不得通婚即两个人最近的共同祖先如果在五代以内即本人、父母、祖父母、曾祖父母、高祖父母则不可通婚。本题就请你帮助一对有情人判断一下他们究竟是否可以成婚输入格式输入第一行给出一个正整数N2 ≤ N ≤104 随后N行每行按以下格式给出一个人的信息本人ID 性别 父亲ID 母亲ID其中ID是5位数字每人不同性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考则相应的ID位置上标记为-1。接下来给出一个正整数K随后K行每行给出一对有情人的ID其间以空格分隔。注意题目保证两个人是同辈每人只有一个性别并且血缘关系网中没有乱伦或隔辈成婚的情况。输出格式对每一对有情人判断他们的关系是否可以通婚如果两人是同性输出Never Mind如果是异性并且关系出了五服输出Yes如果异性关系未出五服输出No。输入样例2400001M01111-100002F022220333300003M022220333300004F044440333300005M044440555500006F044440555500007F066660777700008M066660777700009M000010000200010M000030000600011F000050000700012F000080888800013F000090001100014M000100999900015M000100999900016M100000001200017F-10001200018F110000001300019F111000001800020F000151111000021M111000002000022M00016-100023M100120001700024M00022100139000210002400019000240001100012000220001800001000040001300016000170001500019000210001000011输出样例Never Mind Yes Never Mind No Yes No Yes No No本题思路本题也是一道dfs的衍生题目只不过需要分别对男方和女方分别进行dfs事先设置标志位如果重叠则说明有近亲来源输出No否则“Yes”。#includeiostream#includecstring#includealgorithm#includevectorconstintN100005;using namespace std;intn,k,aid,bid;intflag;vectorintvec[N];//存储关系树intvis[N];//标记关系数组charsex[N];//标记性别intid,fid,mid;//本身id, 父亲id, 母亲idvoiddfs(intx,intnum){vis[x]1;if(num4)return;for(inti0;ivec[x].size();i){if(!vis[vec[x][i]]){dfs(vec[x][i],num1);}else{flag1;}}}intmain(){cinn;while(n--){cinid;getchar();sex[id]getchar();cinfidmid;if(fid!-1){sex[fid]M;vec[id].push_back(fid);}if(mid!-1){sex[mid]F;vec[id].push_back(mid);}}cink;while(k--){cinaidbid;if(sex[aid]sex[bid]){coutNever Mindendl;continue;}flag0;memset(vis,0,sizeof(vis));dfs(aid,0);dfs(bid,0);if(flag1){coutNoendl;}else{coutYesendl;}}return0;}