Similar brothers（深搜）

Question

遇到一道卡了我好久的题（向各位请教，望各位能提供一点思路）
有一无向连通图 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];
    }
}

折腾了半天也只弄出了两个函数

Answer 1

【以下回答由 GPT 生成】

问题已经很清晰了，你需要优化给定的代码，使用深度优先搜索算法来解决问题。问题的目标是找到满足一定条件的节点编号，并按照编号从小到大的顺序进行输出。

你可以将代码分为两部分来进行优化：添加prompt和实现深度优先搜索算法。

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

希望以上解决方案能够满足你的需求。如果你有任何问题，请随时向我提问。

【相关推荐】

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7743683
• 除此之外, 这篇博客: 单素数判断（根号n后再优化）和俄罗斯农民乘法(带证明），以及埃筛的证明中的 简单解释下普遍大家都知道的（给新手），就是为啥只到根号n。最开始其实终止条件是到n/2的，很简单嘛，因为n/2之后不可能存在n的因子，因为最小的因子2乘上一个任何一个大于n/2的数肯定比n大，所以之后不存在因子。那为啥能筛到根号n呢，是因为根号n的平方是n本身，根号n后面如果存在n的因子a，那么一定能在n之前找到n/a这个因子，只要有因子就不是素数了，所以没必要反复筛，前面筛完就已经知道不是素数了 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^