题目思路

这道题目要求对云存储系统中的服务节点进行排序，以便在检测服务状态时，能够优先检测对业务影响较大的节点。具体来说，影响力大的节点是指当该节点发生故障时，会影响更多依赖它的其他节点。为了实现这一目标，我们需要计算每个节点的影响力，即该节点及其所有后继节点的数量。然后，根据影响力对节点进行排序，影响力大的节点排在前面；如果影响力相同，则按节点编号的升序排列。

1. 依赖关系的表示 首先，我们需要理解服务节点之间的依赖关系。题目中指出，每个节点最多只依赖一个其他节点，并且依赖关系不成环。因此，整个系统的依赖关系可以表示为一组树结构或森林结构，每棵树的根节点是没有依赖的节点（f[i] = -1）。

2. 计算每个节点的影响力 影响力大的节点意味着该节点所在的子树规模大，即该节点及其所有后继节点的数量较多。因此，我们可以通过**深度优先搜索（DFS）**遍历每棵树，计算每个节点的子树大小。

具体步骤：

1.构建树结构： 使用一个数组fa[]表示每个节点的父节点。 使用邻接表e[]来存储每个节点的子节点。

2.深度优先搜索（DFS）： 从每棵树的根节点开始，递归计算每个节点的子树大小cnt[]。 cnt[i]表示节点i及其所有后继节点的总数量。

3. 排序节点 计算完每个节点的影响力后，我们需要根据以下规则对节点进行排序：

按影响力降序排列：影响力大的节点排在前面。 按节点编号升序排列：如果两个节点的影响力相同，则编号小的节点排在前面。

4. 输出排序结果 根据排序后的节点顺序输出节点编号，即为检测节点的优先顺序。

5. 时间复杂度分析 构建树结构：遍历所有节点，时间复杂度为O(n)。 DFS计算子树大小：每个节点只被访问一次，时间复杂度为O(n)。 排序：使用快速排序或其他高效排序算法，时间复杂度为O(n log n)。 总体时间复杂度：O(n log n)，适用于n最多为100,000的情况。

类似题目推荐

本质就是考察了一下dfs和自定义排序。较为经典。

LeetCode

1. 112. 路径总和
2. 129. 求根到叶子节点数字之和
3. 236. 二叉树的最近公共祖先

CodeFun2000

1.P1224 携程 2023.04.15-春招-第三题-魔法之树

2.P1196 华为实习 2023-04-19-第二题-塔子哥出城

3.P1159. 2022年清华大学(深圳)保研夏令营机试题-第一题-树上计数

4.P1190 华为实习 2023.04.12-第二题-获取最多食物

5.P1044. 拼多多内推笔试-2023.2.22.投喂珍珠

更多请见:知识点分类-训练-深度优先搜索专栏

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int fa[N];				//节点i的父节点
vector<int> e[N];		//节点i的子节点
int cnt[N];				//节点i的子树中的节点个数
int dfs(int s)		//计算s的 子树中的节点个数
{
	cnt[s] = 1;		//s本身
	for(int g: e[s])	//遍历s的每个子节点
	{
		cnt[s] += dfs(g);	//递归计算每个子节点的子树的节点个数，然后加到s上
	}
	return cnt[s];		//返回s的子树的节点个数
}
int ans[N];
bool cmp(int &x, int &y) {		//重写排序函数，按照子树中节点个数排序，相等时按大小排序
	if(cnt[x] == cnt[y]) return x < y;
	return cnt[x] > cnt[y];
}
int main()
{
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
		cin >> fa[i];		//输入i的父节点
		if(fa[i] != -1) {		//-1代表i没有父节点，此时i为一棵树的根节点
			e[fa[i]].push_back(i);	//添加到父节点的子节点集合中
		}
	}
	for(int i = 0 ; i < n ; i++) {
		ans[i] = i;		//顺便初始化一下排序的值
		if(fa[i] == -1)	//i为一棵树的根节点，从这个点开始遍历
            dfs(i);
	}
	sort(ans, ans+n, cmp);	//排序
	for(int i = 0 ; i < n ; i ++) {
		cout << ans[i] << " \n"[i+1==n];	//输出，" \n"[i+1==n]代表最后一次输出回车，前面输出空格分割
	}
}

python

from collections import defaultdict
n = int(input())
e = defaultdict(list)
a = list(map(int,input().split()))
# 读入 + 存图
for i in range(n):
	if a[i] != -1:
		e[a[i]].append(i)
# cnt 子树大小
cnt = [0] * n
# dfs 求子树大小
def dfs(u):
	cnt[u] = 1
	for v in e[u]:
		dfs(v)
		cnt[u] += cnt[v]
# 按题目要求排序
res = []
for i in range(n):
	if cnt[i] == 0:
		dfs(i)
	res.append([i , cnt[i]])
res.sort(key = lambda x : (-x[1] , x[0]))
print(" ".join(map(str,[x[0] for x in res])))

Java

import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int N = 100010;
    static int n;
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static boolean[] visited = new boolean[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 0; i < N; i++){
            graph.put(i, new ArrayList<>());
        }
        // 读入,存图
        for(int i = 0; i < n; i++){
            int temp = in.nextInt();
            if(temp != -1){
                add(temp, i);
            }
        }
        // dfs 求后继结点个数 , 以二元组形式存储，以便之后的自定义排序
        List<int[]> res = new ArrayList<>();
        for(int i = 0; i < n; i++){
            res.add(new int[]{dfs(i), i});
        }
        // 自定义排序
        Collections.sort(res, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                // 根据题解,优先按后继结点个数降序排序
                if (a[0] != b[0]) {
                    return b[0] - a[0];
                } else { // 相同情况下 按节点编号升序排序
                    return Integer.compare(a[1], b[1]);
                }
            }
        });
        // 输出答案
        for(int[] pair : res){
            System.out.print(pair[1] + " ");
        }
    }
    // 计算后继节点个数
    private static int dfs(int i){
        int count = 0;
        for(int j : graph.get(i)){
            count += dfs(j);
        }
        return count+1;
    }
    private static void add(int a, int b){
        graph.get(a).add(b);
    }
}
// bt  guanam

Go

package main

import (
	"fmt"
	"sort"
)

const N int = 1e5 + 10

var f []int = make([]int, N)
var n int

type node struct {
	id     int
	sonCnt int
}

func dfs(edges [][]int, x int) int {
	if len(edges[x]) == 0 {
		return 1
	}
	res := 1
	for _, v := range edges[x] {
		res += dfs(edges, v)
	}
	return res
}

func main() {
	//构建有向图 计算每个节点的子节点个数 排序
	fmt.Scan(&n)
	//有向图的邻接边
	edges := make([][]int, n)
	for i := range edges {
		edges[i] = make([]int, 0)
	}
	outDegree := make([]int, n) //每个节点的出度
	for i := 0; i < n; i++ {
		fmt.Scan(&f[i])
		if f[i] != -1 {
			edges[f[i]] = append(edges[f[i]], i)
			outDegree[f[i]]++
		}
	}
	cnt := make([]int, n)
	for i := 0; i < n; i++ {
		if outDegree[i] == 0 { //如果出度为0 子节点就只算它自己
			cnt[i] = 1
		} else { //出度不为0 dfs它的所有直接子节点 更新它的总子节点个数
			cnt[i] = dfs(edges, i)
		}
	}
	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].id = i
		nodes[i].sonCnt = cnt[i]
	}
	sort.Slice(nodes, func(i, j int) bool {
		if nodes[i].sonCnt != nodes[j].sonCnt { //子节点数量不同时 按照子节点数量降序排列
			return nodes[i].sonCnt > nodes[j].sonCnt
		}
		return nodes[i].id < nodes[j].id //相同时 按照编号升序排列
	})
	for i := 0; i < n; i++ {
		fmt.Printf("%d", nodes[i].id)
		if i != n-1 {
			fmt.Printf(" ")
		}
	}
}
// by xchen

Js

// 创建 readline interface 实例
const rl = require('readline').createInterface({input: process.stdin});

// 获取 readline 迭代器
const iter = rl[Symbol.asyncIterator]();

// 定义异步函数，并使用 IIFE 函数立即执行
void async function () {
    // 读取第一行输入，n 代表节点个数
    const n = parseInt(await readline());

    // 读取第二行输入，F 代表以空格分隔的每个节点的父节点编号
    const F = (await readline()).split(' ').map(item => parseInt(item));

    // 创建 Map，存放每个节点的父节点后继位置的数组
    const map = new Map();

    // 定义数组存放每个节点所对应的后继结点个数
    const count = [];

    // 遍历每个节点，判断其父节点是否存在，如果存在，则将该节点下标加入其对应的数组中，否则跳过
    for (let i = 0; i < n; i++) {
        if (F[i] !== -1) {
            if (map.has(F[i])) {
                map.set(F[i], [...map.get(F[i]), i]);   // 将该节点下标 push 进去其父节点后继位置的数组中
            }
            else {
                map.set(F[i], [i]);    // 新建一个数组，存放当前节点下标，指定其为其父节点的后继位置
            }
        }
    }

    // 定义深度优先遍历函数，参数分别为 map 和 currV，返回值为当前节点的后继结点个数
    const dfs = (map, currV) => {
        if (!map.has(currV) || map.get(currV) === 0) {   // 当前节点不存在或其没有后继结点，返回 1

            return 1;
        }
        let res = 1;   // res 表示当前节点及其后继结点的总个数
        const edge = map.get(currV);   // 获取当前节点的后继位置数组
        for (let V of edge) {
            res += dfs(map, V);   // 递归计算每个后继结点的后继结点总个数，并将结果加到 res 上
        }
        return res;   // 返回当前节点及其后继结点的总个数
    }

    // 定义二维数组 comp 存放每个节点的下标和其所对应的后继结点个数
    const comp = new Array(n).fill(0).map(item => new Array(2).fill(0));
    const res = [];

    // 遍历每个节点，计算其所对应的后继结点总数并存入 comp 中
    for (let i = 0; i < n; i++) {
        comp[i][0] = i;   // 第一列存放节点下标
        comp[i][1] = dfs(map, i);   // 第二列存放节点的后继结点总个数
    }

    // 对二维数组 comp 进行排序，先按第二列倒序排序，之后按第一列顺序排序
    comp.sort((a, b) => {
        if (a[1] === b[1]) {
            return a[0] - b[0];
        }
        else {
            return b[1] - a[1];
        }
    })

    // 将排序后的节点下标存入 res 数组中
    for (let pair of comp) {
        res.push(pair[0])
    }

    // 输出 res 数组中的元素，以空格分隔
    console.log(res.join(' '))
}()