华为OD机试 新系统 题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
假设你是大型科技公司的数据分析师，负责分析公司内部员工的社交网络。你需要编写一个函数来计算每个员工的影响力分数。影响力分数定义为该员工直接和间接影响的员工数量。
二、输入描述
n：员工总数。
employess:一个二维列表，表示员工的社交网络关系。例如employees[i]是一个包含员工 i 直接影响的员工ID的列表。
备注
employees列表中，* 表示没有直接影响到的员工；员工总数小于20；自身不算分数。
三、输出描述
influenceScores，一个整数数组，表示每个员工的影响力分数。
四、测试用例
测试用例1：
1、输入
4
1
2
3
*
2、输出
3 2 1 0
3、说明
0 -> 1 -> 2 -> 3，所以 0 能影响 1、2、3，共 3 人
1 能影响 2、3，共 2 人
2 能影响 3，共 1 人
3 不能影响任何人，得 0
测试用例2：
1、输入
5
1 2
3
4
*
*
2、输出
4 1 1 0 0
3、说明
0 直接影响 1、2，间接还能影响 3、4，共 4 人
1 影响 3，共 1 人
2 影响 4，共 1 人
3、4 均无影响
五、解题思路
这道题本质上是一个有向图的可达性统计问题。
1、建模
把每个员工看成图中的一个节点。
如果员工 i 直接影响员工 j，就建立一条从 i -> j 的有向边。
这样，题目就转化为：对图中的每个节点，求从它出发可以到达多少个其他节点。
2、求解方式
对每个员工 i，执行一次 DFS（或 BFS）：
- 能直接到达的员工计入影响力
- 能通过别人继续到达的员工，也计入影响力
- 使用 visited 数组避免重复访问，防止环导致死循环
最后统计 visited 中为 true 的个数即可。
六、Java算法源码
publicclassOdTest{/** * 深度优先搜索 * 功能：从当前员工 node 出发，找到所有直接或间接能影响到的员工 * * @param node 当前员工编号 * @param graph 邻接表，graph[i] 存储员工 i 直接影响到的员工 * @param visited 标记数组，visited[j] = true 表示员工 j 已经被当前起点员工影响到 */privatestaticvoiddfs(intnode,List<Integer>[]graph,boolean[]visited){// 遍历当前员工直接影响的所有员工for(intnext:graph[node]){// 如果该员工还没有被访问过，说明是新影响到的员工if(!visited[next]){visited[next]=true;// 继续向下搜索，寻找 next 间接影响到的人dfs(next,graph,visited);}}}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);// 读取员工总数 nintn=Integer.parseInt(sc.nextLine().trim());// 使用邻接表存储社交网络关系// graph[i] 表示员工 i 直接影响的员工集合List<Integer>[]graph=newArrayList[n];for(inti=0;i<n;i++){graph[i]=newArrayList<>();}// 逐行读取每个员工的直接影响关系for(inti=0;i<n;i++){Stringline=sc.hasNextLine()?sc.nextLine().trim():"";// "*" 或空行表示该员工没有直接影响任何人if(line.length()==0||"*".equals(line)){continue;}// 按空格拆分出所有员工编号String[]parts=line.split("\\s+");for(Stringpart:parts){if(part.length()==0){continue;}intv=Integer.parseInt(part);// 做一个简单健壮性保护：// 1. 员工编号必须在 0 ~ n-1 范围内// 2. 自己影响自己不计入图中if(v>=0&&v<n&&v!=i){graph[i].add(v);}}}// 结果数组，ans[i] 表示员工 i 的影响力分数int[]ans=newint[n];// 对每个员工分别做一次 DFSfor(inti=0;i<n;i++){// visited[j] = true 表示从员工 i 出发可以影响到员工 jboolean[]visited=newboolean[n];// 从员工 i 开始搜索dfs(i,graph,visited);// 统计可达员工数量intcount=0;for(booleanv:visited){if(v){count++;}}ans[i]=count;}// 按要求输出，数字之间用空格分隔，不输出多余提示信息for(inti=0;i<n;i++){if(i>0){System.out.print(" ");}System.out.print(ans[i]);}sc.close();}}七、效果展示
1、输入
6
1 2
3 4
4
5
5
*
2、输出
5 3 2 1 1 0
3、说明
0 能影响 1、2、3、4、5，共 5 人
1 能影响 3、4、5，共 3 人
2 能影响 4、5，共 2 人
3 能影响 5，共 1 人
4 能影响 5，共 1 人
5 无影响
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 新系统 200分）
🏆本专栏收录于《华为OD机试（JAVA）真题》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
