品牌设计公司哪家好_郑州妇科医院排行榜_seo优化公司信_独立站建站需要多少钱

题目描述

小明为了调研微服务调用情况，对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;
}