遇到一道卡了我好久的题（向各位请教，望各位能提供一点思路）
有一无向连通图 G（n 个顶点，n - 1条边，点从 1 到 n 依次编号）。当然，你能看出这其实就是一棵树，请找出所有满足以下条件的节点：
该节点不是叶子节点（度不为 0）。
该节点下面所有的子树大小必须相同（如果下面只有一棵子树也默认为相同）。
注意，该树为有根树，你需要先找到它的根才能开始访问其他节点。
输入格式
第一行包含 1 个整数 n。
接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点之间有边相连，其中 u 是 v 的父亲节点。
输出格式
输出共 1 行，包含若干个整数，之间用空格隔开，表示为满足题目要求的节点编号。
注意，输出的顺序要按照编号 从小到大 进行输出。
数据范围
对于 30% 的数据，1 < n ≤ 100；
对于 60% 的数据，1 < n ≤ 2000；
对于 100% 的数据，1 < n ≤ 200000
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs (int u)
{
size[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == root) continue;
dfs(j);
size[u] += size[j];
}
}
折腾了半天也只弄出了两个函数
【以下回答由 GPT 生成】
问题已经很清晰了，你需要优化给定的代码，使用深度优先搜索算法来解决问题。问题的目标是找到满足一定条件的节点编号，并按照编号从小到大的顺序进行输出。
你可以将代码分为两部分来进行优化：添加prompt和实现深度优先搜索算法。
为了让chatgpt更好地理解你的问题，请在回答中添加以下prompt：
问题描述: 给定一个无向连通图G，找出满足一定条件的节点编号。
条件: 1. 节点不是叶子节点。 2. 节点下面的所有子树大小必须相同。
输入: - 整数n：表示节点的数量。 - n-1行，每行包含两个用空格隔开的正整数u和v，表示节点u和节点v之间有一条边相连，其中u是v的父亲节点。
输出: - 若干个整数，用空格隔开，表示满足条件的节点编号，按照编号从小到大的顺序输出。
数据范围: - 对于30%的数据，1 < n ≤ 100； - 对于60%的数据，1 < n ≤ 2000； - 对于100%的数据，1 < n ≤ 200000。
// 声明一个数组用于存储节点的度
int degree[MAXN];
// 创建一个结构体用于存储图的信息
struct Graph {
int n; // 节点数量
vector<vector<int>> adj; // 邻接表，存储节点的相邻节点
};
// 初始化图的信息
void initGraph(Graph& graph, int n) {
graph.n = n;
graph.adj.resize(n + 1);
memset(degree, 0, sizeof(degree));
}
// 添加边
void addEdge(Graph& graph, int u, int v) {
graph.adj[u].push_back(v);
graph.adj[v].push_back(u);
degree[u]++;
degree[v]++;
}
// 深度优先搜索
void dfs(const Graph& graph, int u, vector<int>& result) {
// 遍历节点的相邻节点
for (int v : graph.adj[u]) {
// 如果节点v未被访问过且不是根节点
if (degree[v] > 1 && degree[v] != degree[u]) {
continue;
}
// 记录满足条件的节点编号
result.push_back(v);
// 递归访问子树
dfs(graph, v, result);
}
}
// 主函数
vector<int> findSimilarNodes(int n, vector<vector<int>>& edges) {
// 创建并初始化图的信息
Graph graph;
initGraph(graph, n);
// 添加边
for (auto& edge : edges) {
int u = edge[0];
int v = edge[1];
addEdge(graph, u, v);
}
// 找到根节点
int root = 1;
for (int i = 1; i <= n; i++) {
if (degree[i] > 1) {
root = i;
break;
}
}
// 进行深度优先搜索
vector<int> result;
dfs(graph, root, result);
// 对结果进行排序
sort(result.begin(), result.end());
return result;
}
希望以上解决方案能够满足你的需求。如果你有任何问题，请随时向我提问。
【相关推荐】