当前位置：首页 > news >正文

GESP认证C++编程真题解析 | P10109 [GESP202312 六级] 工作沟通

news 2026/7/30 9:53:14

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P10109 GESP202312 六级] 工作沟通 - 洛谷

【题目描述】

某公司有N NN名员工，编号从0 00至N − 1 N-1N−1。其中，除了0 00号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i ii的员工的直接领导是f i f_ifi。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工x xx可以管理员工y yy，当且仅当x = y x=yx=y，或x = f y x=f_yx=fy，或x xx可以管理f y f_yfy。特别地，0 00号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

【输入】

第一行一个整数N NN，表示员工的数量。

第二行N − 1 N - 1N−1个用空格隔开的正整数，依次为f 1 , f 2 , … f N − 1 f_1,f_2,\dots f_{N−1}f1,f2,…fN−1。

第三行一个整数Q QQ，表示共有Q QQ场合作需要安排。

接下来Q QQ行，每行描述一场合作：开头是一个整数m mm（2 ≤ m ≤ N 2 \le m \le N2≤m≤N），表示参与本次合作的员工数量；接着是m mm个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

【输出】

输出Q QQ行，每行一个整数，依次为每场合作的主持人选。

【输入样例】

5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4

【输出样例】

2 2 0

【算法标签】

《洛谷 P10109 工作沟通》 #图论# #图遍历# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=305;// 最大节点数intn,q;// n: 节点数, q: 查询次数vector<int>g[N];// 邻接表存储树boolst[N];// 访问标记数组// 深度优先搜索，标记从u出发能到达的所有节点voiddfs(intu){st[u]=1;// 标记当前节点for(inti=0;i<g[u].size();i++){st[g[u][i]]=1;// 标记子节点dfs(g[u][i]);// 递归遍历}}intmain(){// 输入节点数cin>>n;// 输入树的n-1条边for(inti=1;i<n;i++){intx;cin>>x;// 节点i的父节点g[x].push_back(i);// 建立从父节点x到子节点i的边}// 输入查询次数cin>>q;// 处理每个查询while(q--){intm;// 查询中包含的节点数cin>>m;vector<int>ve;// 存储查询节点// 输入查询节点for(inti=1;i<=m;i++){intx;cin>>x;ve.push_back(x);}// 从大到小遍历节点编号for(inti=n-1;i>=0;i--){// 重置访问标记memset(st,0,sizeof(st));// 从节点i开始DFS，标记所有可达节点dfs(i);// 检查是否所有查询节点都被标记boolflag=1;for(intj=0;j<ve.size();j++){if(st[ve[j]]==false)// 有节点未标记{flag=0;break;}}// 如果所有查询节点都在i的子树中if(flag){cout<<i<<endl;// 输出当前节点编号break;// 找到答案，退出循环}}}return0;}