上期我们聊到,你为了帮助塔子哥维护云服务器而大打出手。如今,云服务器已经平稳运行并给用户们提供了一系列不错的服务,但是塔子哥仍花了很多时间在运维和数据分析上。
更形式的,塔子哥为了调研微服务调用情况,对n个微服务调用数据进行了采集分析,微服务使用数字0至n−1进行编号,给你一个下标从0开始的数组edges,其中edges[i]表示存在一条从微服务i到微服务edges[i]的接口调用。
为了更好的维护,塔子哥将形成1个环的多个微服务称为微服务群组,一个微服务群组的所有微服务数量为L,能够访问到该微服务群组的微服务数量为V,这个微服务群组的内聚值H=L−V。
在这道题中,我们需要处理一个包含 n
个微服务的调用关系数组 edges
,其中每个微服务通过数组值指向另一个微服务。我们的目标是识别所有的微服务环群组,计算每个环的内聚值 H = L - V(L 为环中微服务的数量,V 为可以访问该环的其他微服务数量),并根据 H 值进行排序(当 H 值相同时,按环中最大微服务编号排序)。最后,输出 H 值最大的环,确保输出顺序是从环中编号最小的微服务开始。输入包含一个整数 n
和一个长度为 n
的数组 edges
,输出为满足条件的微服务编号,以空格分隔。
思路:BFS遍历
1,6,3组成了微服务群组(环) a1,L1值为3,编号为4、9的2个微服务可以访问到a1,因此√1值为2,H1为L1V1 =1;
0,2,10,5组成了微服务群组 (环) a2,L2值为4,编号为7、8、11的3个微服务可以访问到2,因此v2值为3,H2为L2-V2=1;