机试题——微服务群组

标题形貌

小明为了调研微服务调用情况，对n个微服务调用数据举行了收罗分析。微服务利用数字0到n-1举行编号，给定一个数组edges，此中edges体现存在一条从微服务i到微服务edges的接口调用。
为了更好地维护，小明将形成环的多个微服务称为微服务群组。一个微服务群组的全部微服务数量为L，可以大概访问到该微服务群组的微服务数量为V，这个微服务群组的内聚值为H = L - V。
已知提供的数据中有1个或多个微服务群组，请按照内聚值H的结果从大到小的次序对全部微服务群组排序（H相称时，取环中最大的数举行比力），输出排在第一的微服务群组，输出时每个微服务群组输出的起始编号为环中最小的数。
输入形貌

• 第一行：一个整数n，体现有n个微服务（2 ≤ n ≤ 10^5）。
  
• 第二行：数组edges，此中edges体现存在一条从微服务i到微服务edges的接口调用（0 ≤ edges ≤ n-1，edges ≠ i）。
  

输出形貌

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

1. 4
2. 3 3 0 2

复制代码

1. 0 3 2

复制代码

0，3，2构成了微服务群组（环）a，其L值为3，只有编号为1的一个微服务可以访问到a，因此V值为1，内聚值H = L - V = 2。

1. 12
2. 2 6 10 1 6 0 3 0 5 4 5 8

复制代码

1. 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%）

1. #include<iostream>
2. #include<cstdio>
3. #include<cstring>
4. #include<cmath>
5. #include<map>
6. #include<algorithm>
7. #include<string>
8. #include<vector>
9. #include<unordered_map>
10. #include<unordered_set>
11. #include<queue>
12. #include<set>
13. #include<list>
14. #include<sstream>
15. #include<bitset>
16. #include<stack>
17. #include<climits>
18. #include<iomanip>
19. #include<cstdint>
20. using namespace std;
22. // 用于存储图的边关系
23. unordered_map<int, int> mp;
25. // 定义微服务群组的结构体
26. struct node {
27.     vector<int> w; // 微服务的环
28.     int v; // 其他微服务可访问数量
29.     int maxid; // 环中编号最大的节点
30.     int size; // 环的大小
31. };
33. // 临时遍历的栈，用于记录DFS路径
34. vector<int> temp;
36. // 存储所有微服务群组
37. vector<node> res;
39. // 状态表，记录每个节点的访问状态
40. unordered_map<int, int> states;
42. // 状态定义：
43. // 0 - 未遍历
44. // 1 - 已完全遍历
45. // 2 - 正在遍历（用于检测环）
46. void dfs(int cur, unordered_map<int, int>& states) {
47.     if (states[cur] == 1) {
48.         // 如果当前节点已完全遍历，直接返回
49.         return;
50.     }
51.     if (states[cur] == 2) {
52.         // 如果当前节点正在遍历中，说明遇到了环
53.         node tres;
54.         auto index = find(temp.begin(), temp.end(), cur); // 找到环的起始位置
55.         tres.w = {};
56.         while (index != temp.end()) {
57.             tres.w.push_back(*index); // 将环中的节点加入到当前群组
58.             index++;
59.         }
60.         tres.maxid = 0; // 初始化环中最大编号
61.         tres.v = 0; // 初始化可访问数量
62.         res.push_back(tres); // 将当前群组加入到结果中
63.         return;
64.     }
65.     temp.push_back(cur); // 将当前节点加入到临时路径
66.     states[cur] = 2; // 标记当前节点为正在遍历
67.     dfs(mp[cur], states); // 递归访问下一个节点
68.     temp.pop_back(); // 回溯，移除当前节点
69.     states[cur] = 1; // 标记当前节点为已完全遍历
70. }
72. // 从最小的节点开始遍历环，确保环的输出顺序正确
73. void find_w(int root, vector<int>& temp) {
74.     if (temp.size() && temp[0] == root) return; // 如果已经遍历到根节点，结束
75.     temp.push_back(root); // 将当前节点加入到路径
76.     find_w(mp[root], temp); // 递归访问下一个节点
77. }
79. // 比较函数，用于排序
80. bool cmp(node& a, node& b) {
81.     if ((a.size - a.v) != (b.size - b.v)) {
82.         // 如果内聚值不同，按内聚值从大到小排序
83.         return (a.size - a.v) > (b.size - b.v);
84.     }
85.     // 如果内聚值相同，按环中最大编号从大到小排序
86.     return a.maxid > b.maxid;
87. }
89. int main() {
90.     ios::sync_with_stdio(false);
91.     cin.tie(nullptr);
92.     int n;
93.     cin >> n; // 输入微服务的数量
94.     for (int i = 0; i < n; i++) {
95.         int x;
96.         cin >> x; // 输入每个微服务的调用关系
97.         mp[i] = x; // 构建图
98.     }
99.     for (int i = 0; i < n; i++) {
100.         // 从每个节点开始DFS，确保找到所有环
101.         dfs(i, states);
102.     }
103.     // 初始化每个节点的群组标记
104.     unordered_map<int, int> is;
105.     for (int i = 0; i < n; i++) is[i] = -1;
106.     for (int i = 0; i < res.size(); i++) {
107.         int minnid = INT_MAX;
108.         for (int j = 0; j < res[i].w.size(); j++) {
109.             res[i].maxid = max(res[i].w[j], res[i].maxid); // 更新环中最大编号
110.             minnid = min(res[i].w[j], minnid); // 更新环中最小编号
111.             is[res[i].w[j]] = i; // 标记当前节点属于哪个群组
112.         }
113.         // 从环中最小的节点开始重新遍历环，确保输出顺序正确
114.         res[i].w.clear();
115.         find_w(minnid, res[i].w);
116.         res[i].size = res[i].w.size(); // 更新环的大小
117.     }
118.     // 计算每个群组的可访问数量
119.     for (int i = 0; i < n; i++) {
120.         if (is[i] == -1) {
121.             // 如果当前节点不属于任何群组，检查它可以访问的群组
122.             int ne = mp[i];
123.             while (is[ne] == -1) {
124.                 ne = mp[ne]; // 沿着调用链找到属于某个群组的节点
125.             }
126.         }
127.     }
128.     // 按内聚值和环中最大编号排序
129.     sort(res.begin(), res.end(), cmp);
130.     // 输出排在第一的微服务群组
131.     for (int i = 0; i < res[0].w.size(); i++) {
132.         cout << res[0].w[i] << " ";
133.     }
134.     return 0;
135. }

复制代码