华为OD机试 - 统计员工影响力分数（Python/JS/C/C++ 新系统 200分）

华为OD机试 新系统 统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

假设你是大型科技公司的数据分析师，负责分析公司内部员工的社交网络。你需要编写一个函数来计算每个员工的影响力分数。影响力分数定义为该员工直接和间接影响的员工数量。

二、输入描述

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 的个数即可。

六、Python算法源码

importsys# 深度优先搜索：从当前员工出发，找到所有可影响到的员工defdfs(node,graph,visited):fornxtingraph[node]:ifnotvisited[nxt]:visited[nxt]=Truedfs(nxt,graph,visited)defmain():lines=sys.stdin.read().splitlines()ifnotlines:return# 读取员工总数n=int(lines[0].strip())# 邻接表：graph[i] 表示员工 i 直接影响到的员工graph=[[]for_inrange(n)]# 读取每个员工的直接影响关系foriinrange(n):line=lines[i+1].strip()ifi+1<len(lines)else""# "*" 或空行表示没有直接影响对象ifnotlineorline=="*":continueforsinline.split():v=int(s)# 做边界保护，并排除自己影响自己if0<=v<nandv!=i:graph[i].append(v)ans=[]# 对每个员工分别进行 DFSforiinrange(n):visited=[False]*n dfs(i,graph,visited)# True 的个数就是影响力分数ans.append(str(sum(visited)))# 按题意输出sys.stdout.write(" ".join(ans))if__name__=="__main__":main()

七、JavaScript算法源码

constfs=require("fs");constinput=fs.readFileSync(0,"utf8").split(/\r?\n/);if(input.length>0&&input[0].trim()!==""){// 员工总数constn=Number(input[0].trim());// 邻接表：graph[i] 表示员工 i 直接影响到的员工constgraph=Array.from({length:n},()=>[]);// 构建图for(leti=0;i<n;i++){constline=(input[i+1]||"").trim();// "*" 或空行表示没有直接影响任何人if(!line||line==="*"){continue;}constarr=line.split(/\s+/);for(constsofarr){constv=Number(s);// 边界保护，并排除自己影响自己if(v>=0&&v<n&&v!==i){graph[i].push(v);}}}// 深度优先搜索functiondfs(node,visited){for(constnxtofgraph[node]){if(!visited[nxt]){visited[nxt]=true;dfs(nxt,visited);}}}constans=[];// 对每个员工计算影响力for(leti=0;i<n;i++){constvisited=Array(n).fill(false);dfs(i,visited);// 统计能影响到的人数constcount=visited.filter(Boolean).length;ans.push(String(count));}// 按题意输出process.stdout.write(ans.join(" "));}

八、C算法源码

#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN25#defineMAXLINE512// graph[i][k] 表示员工 i 直接影响到的第 k 个员工intgraph[MAXN][MAXN];// sizes[i] 表示员工 i 的直接影响人数intsizes[MAXN];// 员工总数intn;/** * 深度优先搜索 * 功能：从 node 出发，标记所有可影响到的员工 */voiddfs(intnode,intvisited[]){for(inti=0;i<sizes[node];i++){intnxt=graph[node][i];if(!visited[nxt]){visited[nxt]=1;dfs(nxt,visited);}}}intmain(){// 读取员工总数if(scanf("%d",&n)!=1){return0;}// 吃掉换行符，方便后续 fgets 读整行getchar();charline[MAXLINE];// 构图for(inti=0;i<n;i++){sizes[i]=0;if(!fgets(line,sizeof(line),stdin)){line[0]='\0';}// 去掉行末换行符line[strcspn(line,"\r\n")]='\0';// "*" 或空行表示没有直接影响任何人if(strlen(line)==0||strcmp(line,"*")==0){continue;}// 按空格拆分char*token=strtok(line," ");while(token!=NULL){intv=atoi(token);// 边界保护，并排除自己影响自己if(v>=0&&v<n&&v!=i){graph[i][sizes[i]++]=v;}token=strtok(NULL," ");}}// 对每个员工做一次 DFSfor(inti=0;i<n;i++){intvisited[MAXN]={0};dfs(i,visited);intcount=0;for(intj=0;j<n;j++){count+=visited[j];}if(i>0){printf(" ");}printf("%d",count);}return0;}

九、C++算法源码

#include<bits/stdc++.h>usingnamespacestd;/** * 深度优先搜索 * 从当前员工 node 出发，找到所有可影响到的员工 */voiddfs(intnode,constvector<vector<int>>&graph,vector<int>&visited){for(intnxt:graph[node]){if(!visited[nxt]){visited[nxt]=1;dfs(nxt,graph,visited);}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string firstLine;if(!getline(cin,firstLine)||firstLine.empty()){return0;}// 员工总数intn=stoi(firstLine);// 邻接表vector<vector<int>>graph(n);// 读取每个员工的直接影响关系for(inti=0;i<n;i++){string line;if(!getline(cin,line)){line="";}// "*" 或空行表示没有直接影响任何人if(line.empty()||line=="*"){continue;}stringstreamss(line);intv;// 解析该行所有员工编号while(ss>>v){// 边界保护，并排除自己影响自己if(v>=0&&v<n&&v!=i){graph[i].push_back(v);}}}// 计算每个员工的影响力分数for(inti=0;i<n;i++){vector<int>visited(n,0);dfs(i,graph,visited);intcount=accumulate(visited.begin(),visited.end(),0);if(i>0){cout<<" ";}cout<<count;}return0;}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 新系统 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。