有人能告诉我这个代码哪里错了吗?他报错
2024-08-17 11:54:43
发布于:上海
21阅读
0回复
0点赞
递归报错
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1001;
vector<int> tree[MAXN];
int value[MAXN]; // 存储节点上的数字
int nodeOrder[MAXN]; // 存储最终的节点顺序
bool deletedEdge[MAXN][MAXN]; // 标记边是否已删除
// DFS辅助函数,返回当前节点的深度
int dfs(int currentNode, int parent, vector<int>& order, int& depth) {
int minVal = value[currentNode];
int minPos = order[depth];
deletedEdge[currentNode][parent] = true;
for (int child : tree[currentNode]) {
if (child != parent && !deletedEdge[currentNode][child]) {
int childDepth = dfs(child, currentNode, order, depth + 1);
if (value[child] < minVal) {
minVal = value[child];
minPos = child;
}
}
}
// 交换值,如果需要
if (minPos != currentNode) {
swap(value[currentNode], value[minPos]);
deletedEdge[currentNode][minPos] = true;
deletedEdge[minPos][currentNode] = true;
}
order[depth] = minPos;
return depth;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> value[i];
}
// 构建树
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
vector<int> order(n);
for (int i = 0; i < n; ++i) order[i] = i + 1;
fill(deletedEdge, deletedEdge + MAXN * MAXN, false);
dfs(1, -1, order, 0);
// 输出结果
for (int i = 1; i <= n; ++i) {
nodeOrder[value[i]] = i;
}
for (int i = 1; i <= n; ++i) {
cout << nodeOrder[i] << " ";
}
cout << endl;
}
return 0;
}
全部评论 1
哥们chat代码超肥
2024-08-17 来自 广东
0
有帮助,赞一个