目录

机试题微服务群组

机试题——微服务群组

题目描述

小明为了调研微服务调用情况,对 n 个微服务调用数据进行了采集分析。微服务使用数字 0n-1 进行编号,给定一个数组 edges ,其中 edges[i] 表示存在一条从微服务 i 到微服务 edges[i] 的接口调用。

为了更好地维护,小明将形成环的多个微服务称为 微服务群组 。一个微服务群组的所有微服务数量为 L ,能够访问到该微服务群组的微服务数量为 V ,这个微服务群组的 内聚值H = L - V

已知提供的数据中有1个或多个微服务群组,请按照内聚值 H 的结果从大到小的顺序对所有微服务群组排序( H 相等时,取环中最大的数进行比较),输出排在第一的微服务群组,输出时每个微服务群组输出的起始编号为环中最小的数。

输入描述

  1. 第一行:一个整数 n ,表示有 n 个微服务( 2 ≤ n ≤ 10^5 )。
  2. 第二行:数组 edges ,其中 edges[i] 表示存在一条从微服务 i 到微服务 edges[i] 的接口调用( 0 ≤ edges[i] ≤ n-1edges[i] ≠ i )。

输出描述

输出排在第一的微服务群组的编号数组,按照环的访问顺序输出,起始编号为环中最小的数,数字以空格分隔。

用例输入

4
3 3 0 2
0 3 2

032 组成了微服务群组(环) 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

163 组成了微服务群组(环) a1L1 值为 3 ,编号为 492 个微服务可以访问到 a1 ,因此 V1 值为 2H1 = L1 - V1 = 1

02105 组成了微服务群组(环) a2L2 值为 4 ,编号为 78113 个微服务可以访问到 a2 ,因此 V2 值为 3H2 = L2 - V2 = 1

内聚值 H1 = H2 ,但 a2 中最大编号为 10 ,大于 a1 中的最大编号 6 ,因此输出 a2

解题思路(65%)

  1. 问题建模

    • 该问题可以看作是一个 图论问题 ,目标是找到所有微服务群组(环)并计算其内聚值 H
    • 使用深度优先搜索(DFS)找到所有环,并记录每个环的访问顺序。
  2. 数据结构

    • 使用 unordered_map<int, int> 存储图的边关系。
    • 使用 vector<node> 存储所有微服务群组,其中 node 结构体包含:
      • w :环中的微服务编号。
      • v :可以访问该环的微服务数量。
      • maxid :环中编号最大的微服务。
      • size :环的大小。
  3. DFS遍历

    • 使用DFS找到所有环,并记录每个环的访问顺序。
    • 使用状态数组 states 记录每个节点的访问状态:
      • 0 :未访问。
      • 1 :已完全访问。
      • 2 :正在访问(用于检测环)。
  4. 计算内聚值

    • 对于每个环,计算其内聚值 H = L - V
    • 计算每个环的 V 值,即可以访问该环的微服务数量。
  5. 排序

    • 按内聚值 H 从大到小排序。
    • 如果 H 值相同,按环中最大编号从大到小排序。
  6. 输出结果

    • 输出排在第一的微服务群组,起始编号为环中最小的数。

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;
}