机试题微服务群组
机试题——微服务群组
题目描述
小明为了调研微服务调用情况,对
n
个微服务调用数据进行了采集分析。微服务使用数字
0
到
n-1
进行编号,给定一个数组
edges
,其中
edges[i]
表示存在一条从微服务
i
到微服务
edges[i]
的接口调用。
为了更好地维护,小明将形成环的多个微服务称为
微服务群组
。一个微服务群组的所有微服务数量为
L
,能够访问到该微服务群组的微服务数量为
V
,这个微服务群组的
内聚值
为
H = L - V
。
已知提供的数据中有1个或多个微服务群组,请按照内聚值
H
的结果从大到小的顺序对所有微服务群组排序(
H
相等时,取环中最大的数进行比较),输出排在第一的微服务群组,输出时每个微服务群组输出的起始编号为环中最小的数。
输入描述
- 第一行:一个整数
n
,表示有n
个微服务(2 ≤ n ≤ 10^5
)。 - 第二行:数组
edges
,其中edges[i]
表示存在一条从微服务i
到微服务edges[i]
的接口调用(0 ≤ edges[i] ≤ n-1
,edges[i] ≠ i
)。
输出描述
输出排在第一的微服务群组的编号数组,按照环的访问顺序输出,起始编号为环中最小的数,数字以空格分隔。
用例输入
4
3 3 0 2
0 3 2
0
,
3
,
2
组成了微服务群组(环)
a
,其
L
值为
3
,只有编号为
1
的一个微服务可以访问到
a
,因此
V
值为
1
,内聚值
H = L - V = 2
。
12
2 6 10 1 6 0 3 0 5 4 5 8
0 2 10 5
1
,
6
,
3
组成了微服务群组(环)
a1
,
L1
值为
3
,编号为
4
、
9
的
2
个微服务可以访问到
a1
,因此
V1
值为
2
,
H1 = L1 - V1 = 1
。
0
,
2
,
10
,
5
组成了微服务群组(环)
a2
,
L2
值为
4
,编号为
7
、
8
、
11
的
3
个微服务可以访问到
a2
,因此
V2
值为
3
,
H2 = L2 - V2 = 1
。
内聚值
H1 = H2
,但
a2
中最大编号为
10
,大于
a1
中的最大编号
6
,因此输出
a2
。
解题思路(65%)
问题建模 :
- 该问题可以看作是一个
图论问题
,目标是找到所有微服务群组(环)并计算其内聚值
H
。 - 使用深度优先搜索(DFS)找到所有环,并记录每个环的访问顺序。
- 该问题可以看作是一个
图论问题
,目标是找到所有微服务群组(环)并计算其内聚值
数据结构 :
- 使用
unordered_map<int, int>
存储图的边关系。 - 使用
vector<node>
存储所有微服务群组,其中node
结构体包含:w
:环中的微服务编号。v
:可以访问该环的微服务数量。maxid
:环中编号最大的微服务。size
:环的大小。
- 使用
DFS遍历 :
- 使用DFS找到所有环,并记录每个环的访问顺序。
- 使用状态数组
states
记录每个节点的访问状态:0
:未访问。1
:已完全访问。2
:正在访问(用于检测环)。
计算内聚值 :
- 对于每个环,计算其内聚值
H = L - V
。 - 计算每个环的
V
值,即可以访问该环的微服务数量。
- 对于每个环,计算其内聚值
排序 :
- 按内聚值
H
从大到小排序。 - 如果
H
值相同,按环中最大编号从大到小排序。
- 按内聚值
输出结果 :
- 输出排在第一的微服务群组,起始编号为环中最小的数。
100%需要使用Tarjan 算法
代码(65%)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
#include<iomanip>
#include<cstdint>
using namespace std;
// 用于存储图的边关系
unordered_map<int, int> mp;
// 定义微服务群组的结构体
struct node {
vector<int> w; // 微服务的环
int v; // 其他微服务可访问数量
int maxid; // 环中编号最大的节点
int size; // 环的大小
};
// 临时遍历的栈,用于记录DFS路径
vector<int> temp;
// 存储所有微服务群组
vector<node> res;
// 状态表,记录每个节点的访问状态
unordered_map<int, int> states;
// 状态定义:
// 0 - 未遍历
// 1 - 已完全遍历
// 2 - 正在遍历(用于检测环)
void dfs(int cur, unordered_map<int, int>& states) {
if (states[cur] == 1) {
// 如果当前节点已完全遍历,直接返回
return;
}
if (states[cur] == 2) {
// 如果当前节点正在遍历中,说明遇到了环
node tres;
auto index = find(temp.begin(), temp.end(), cur); // 找到环的起始位置
tres.w = {};
while (index != temp.end()) {
tres.w.push_back(*index); // 将环中的节点加入到当前群组
index++;
}
tres.maxid = 0; // 初始化环中最大编号
tres.v = 0; // 初始化可访问数量
res.push_back(tres); // 将当前群组加入到结果中
return;
}
temp.push_back(cur); // 将当前节点加入到临时路径
states[cur] = 2; // 标记当前节点为正在遍历
dfs(mp[cur], states); // 递归访问下一个节点
temp.pop_back(); // 回溯,移除当前节点
states[cur] = 1; // 标记当前节点为已完全遍历
}
// 从最小的节点开始遍历环,确保环的输出顺序正确
void find_w(int root, vector<int>& temp) {
if (temp.size() && temp[0] == root) return; // 如果已经遍历到根节点,结束
temp.push_back(root); // 将当前节点加入到路径
find_w(mp[root], temp); // 递归访问下一个节点
}
// 比较函数,用于排序
bool cmp(node& a, node& b) {
if ((a.size - a.v) != (b.size - b.v)) {
// 如果内聚值不同,按内聚值从大到小排序
return (a.size - a.v) > (b.size - b.v);
}
// 如果内聚值相同,按环中最大编号从大到小排序
return a.maxid > b.maxid;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n; // 输入微服务的数量
for (int i = 0; i < n; i++) {
int x;
cin >> x; // 输入每个微服务的调用关系
mp[i] = x; // 构建图
}
for (int i = 0; i < n; i++) {
// 从每个节点开始DFS,确保找到所有环
dfs(i, states);
}
// 初始化每个节点的群组标记
unordered_map<int, int> is;
for (int i = 0; i < n; i++) is[i] = -1;
for (int i = 0; i < res.size(); i++) {
int minnid = INT_MAX;
for (int j = 0; j < res[i].w.size(); j++) {
res[i].maxid = max(res[i].w[j], res[i].maxid); // 更新环中最大编号
minnid = min(res[i].w[j], minnid); // 更新环中最小编号
is[res[i].w[j]] = i; // 标记当前节点属于哪个群组
}
// 从环中最小的节点开始重新遍历环,确保输出顺序正确
res[i].w.clear();
find_w(minnid, res[i].w);
res[i].size = res[i].w.size(); // 更新环的大小
}
// 计算每个群组的可访问数量
for (int i = 0; i < n; i++) {
if (is[i] == -1) {
// 如果当前节点不属于任何群组,检查它可以访问的群组
int ne = mp[i];
while (is[ne] == -1) {
ne = mp[ne]; // 沿着调用链找到属于某个群组的节点
}
res[is[ne]].v++; // 增加群组的可访问数量
}
}
// 按内聚值和环中最大编号排序
sort(res.begin(), res.end(), cmp);
// 输出排在第一的微服务群组
for (int i = 0; i < res[0].w.size(); i++) {
cout << res[0].w[i] << " ";
}
return 0;
}