屯昌县网站建设_网站建设公司_MySQL_seo优化

统计员工影响力分数

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

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

输入描述

n：员工总数。

employess:一个二维列表，表示员工的社交网络关系。例如employees[i]是一个包含员工i直接影响的员工ID的列表。

备注

employees列表中，* 表示没有直接影响到的员工；员工总数小于20；自身不算分数。

输出描述

influenceScores，一个整数数组，表示每个员工的影响力分数。

用例1

输入

4 1 2 3 *

输出

3 2 1 0

用例2

输入

5 1 2 3 4 * *

输出

4 1 1 0 0

用例3

输入

6 1 2 3 4 5 0 *

输出

5 2 5 1 5 0

题解

思路：DFS算法求解

1. 处理输入，将每个人的可以直接影响的员工使用数组保存。
2. 枚举[0,n-1]员工分别递归计算可直接和间接影响的人数，递归逻辑还是比较简单的，可参照下面代码逻辑，不过递归主要注意两点即可
   1. 题目没有要求影响不成环,所以需要定义visisted数组进行去重。
   2. 影响不包含本身，所以递归开始时直接将自身visisted设置为true.
3. 按题目要求输出每个员工影响人数。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } int dfs(int index, vector<bool>& visited, vector<vector<int>>& employees) { int cnt = 0; for (auto v : employees[index]) { if (visited[v]) { continue; } visited[v] = true; cnt += 1; cnt += dfs(v, visited, employees); } return cnt; } int main() { int n; cin >> n; // 忽略换行符 cin.ignore(); vector<vector<int>> employees(n); vector<int> res(n, -1); for (int i = 0; i < n; i++) { string line; getline(cin, line); // 直接确定为0 if (line == "*") { res[i] = 0; continue; } employees[i] = split(line, " "); } // DFS影响人数 for (int i = 0; i < n; i++) { if (employees[i].empty()) { res[i] = 0; continue; } vector<bool> visited(n, false); // 自己不算 visited[i] = true; res[i] = dfs(i, visited, employees); } // 输出结果 for (int i = 0; i < n; i++) { if (i != 0) { cout << " "; } cout << res[i]; } return 0; }

JAVA

import java.io.*; import java.util.*; public class Main { // DFS 统计影响人数 static int dfs(int index, boolean[] visited, List<List<Integer>> employees) { int cnt = 0; for (int v : employees.get(index)) { if (visited[v]) continue; visited[v] = true; cnt += 1; cnt += dfs(v, visited, employees); } return cnt; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); List<List<Integer>> employees = new ArrayList<>(); for (int i = 0; i < n; i++) employees.add(new ArrayList<>()); int[] res = new int[n]; Arrays.fill(res, -1); for (int i = 0; i < n; i++) { String line = br.readLine(); if (line.equals("*")) { res[i] = 0; continue; } String[] parts = line.split(" "); for (String p : parts) { employees.get(i).add(Integer.parseInt(p)); } } // 对每个员工做一次 DFS for (int i = 0; i < n; i++) { if (employees.get(i).isEmpty()) { res[i] = 0; continue; } boolean[] visited = new boolean[n]; visited[i] = true; // 自己不算 res[i] = dfs(i, visited, employees); } // 输出 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (i > 0) sb.append(" "); sb.append(res[i]); } System.out.println(sb); } }

Python

importsys sys.setrecursionlimit(10**7)# DFS 统计影响人数defdfs(index,visited,employees):cnt=0forvinemployees[index]:ifvisited[v]:continuevisited[v]=Truecnt+=1cnt+=dfs(v,visited,employees)returncntdefmain():n=int(sys.stdin.readline())employees=[[]for_inrange(n)]res=[-1]*nforiinrange(n):line=sys.stdin.readline().strip()ifline=="*":res[i]=0continueemployees[i]=list(map(int,line.split()))# 对每个员工做 DFSforiinrange(n):ifnotemployees[i]:res[i]=0continuevisited=[False]*n visited[i]=True# 自己不算res[i]=dfs(i,visited,employees)print(" ".join(map(str,res)))if__name__=="__main__":main()

JavaScript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on("line",line=>lines.push(line));rl.on("close",()=>{letidx=0;constn=parseInt(lines[idx++]);constemployees=Array.from({length:n},()=>[]);constres=Array(n).fill(-1);for(leti=0;i<n;i++){constline=lines[idx++].trim();if(line==="*"){res[i]=0;continue;}employees[i]=line.split(" ").map(Number);}// DFS 统计影响人数functiondfs(index,visited){letcnt=0;for(constvofemployees[index]){if(visited[v])continue;visited[v]=true;cnt+=1;cnt+=dfs(v,visited);}returncnt;}for(leti=0;i<n;i++){if(employees[i].length===0){res[i]=0;continue;}constvisited=Array(n).fill(false);visited[i]=true;// 自己不算res[i]=dfs(i,visited);}console.log(res.join(" "));});

Go

packagemainimport("bufio""fmt""os""strconv""strings")// DFS 统计影响人数funcdfs(indexint,visited[]bool,employees[][]int)int{cnt:=0for_,v:=rangeemployees[index]{ifvisited[v]{continue}visited[v]=truecnt++cnt+=dfs(v,visited,employees)}returncnt}funcmain(){in:=bufio.NewReader(os.Stdin)varnintfmt.Fscanln(in,&n)employees:=make([][]int,n)res:=make([]int,n)fori:=0;i<n;i++{res[i]=-1}fori:=0;i<n;i++{line,_:=in.ReadString('\n')line=strings.TrimSpace(line)ifline=="*"{res[i]=0continue}parts:=strings.Split(line," ")for_,p:=rangeparts{val,_:=strconv.Atoi(p)employees[i]=append(employees[i],val)}}fori:=0;i<n;i++{iflen(employees[i])==0{res[i]=0continue}visited:=make([]bool,n)visited[i]=true// 自己不算res[i]=dfs(i,visited,employees)}// 输出writer:=bufio.NewWriter(os.Stdout)fori:=0;i<n;i++{ifi>0{fmt.Fprint(writer," ")}fmt.Fprint(writer,res[i])}writer.Flush()}