树上好点问题 - C++ 代码实现与优化 - 常规

树上好点问题 - C++ 代码实现与优化

问题描述:

给定一棵树，其 N 个顶点的编号为 1 到 N 。第 i 条边连接顶点 A[i] 和顶点 B[i] 。顶点 i 的颜色为 C[i] 。如果从顶点 1 到顶点 x 的路径上（最短路径），不包含与点 x 相同颜色的点（顶点 x 本身除外），我们称顶点 x 为好点。按照升序输出所有好点。

输入:

第一行输入一个正整数 N，表示顶点的数量。第二行输入 N 个正整数 C[i]，分别表示每个点的颜色。之后 N-1 行，每行输入两个正整数 A[i],B[i] 表示一条树边。其中 2≤N≤1e5，1≤C[i]≤1e5，保证给定的图是一棵树。

输出:

输出使用换行符作为分隔符，按升序输出所有好点的编号。

样例输入:

6
2 7 1 8 2 8
1 2
3 6
3 2
4 3
2 5

样例输出:

数据范围限制:

对于 17% 的数据， 2 ≤ N ≤ 10 ；
对于 33% 的数据， 2 ≤ N ≤ 3000 ；
对于 100% 的数据， 2 ≤ N ≤ 10^5 ,1 ≤ C[i] ≤ 10^5 ,1 ≤ A[i],B[i] ≤ N ，保证给定的图是一棵树。

使用 C++。

思路：

首先需要构建一棵树，可以使用邻接表来表示图。然后从根节点开始进行深度优先搜索，对每个节点进行判断，如果满足条件（即该节点与路径上的节点颜色不相同），则将其加入到好点集合中。最后对好点集合进行排序，按照升序输出。

具体实现步骤如下：

定义一个结构体 Node，表示每个节点，包括节点编号、颜色和邻接表。
定义一个 vector 数组 nodes，用来存储所有节点信息。
定义一个 vector 数组 goodNodes，用来存储所有好点的编号。
定义一个 bool 数组 visited，用来标记节点是否被访问过。
定义一个函数 dfs，用来进行深度优先搜索。在 dfs 函数中，首先将当前节点标记为已访问，然后对当前节点的邻接表进行遍历，对于每个邻接节点，如果其颜色与当前路径上的节点颜色不相同，则将其加入到好点集合中，并递归调用 dfs 函数。
在主函数中，首先读入输入数据，构建树。然后调用 dfs 函数进行深度优先搜索，并将所有好点的编号保存到 goodNodes 数组中。最后对 goodNodes 数组进行排序，并按照升序输出。

时间复杂度分析：

构建树的时间复杂度为 O(N)。
深度优先搜索的时间复杂度为 O(N)。
排序的时间复杂度为 O(NlogN)。

总的时间复杂度为 O(NlogN)。

空间复杂度分析：

邻接表的空间复杂度为 O(N)。
visited 数组的空间复杂度为 O(N)。
goodNodes 数组的空间复杂度为 O(N)。

总的空间复杂度为 O(N)。

代码实现如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 节点结构体
struct Node {
    int id; // 节点编号
    int color; // 节点颜色
    vector<int> adj; // 邻接表
};

int main() {
    int n; // 顶点数量
    cin >> n;

    // 存储所有节点信息
    vector<Node> nodes(n + 1); 
    for (int i = 1; i <= n; i++) {
        nodes[i].id = i; // 设置节点编号
        cin >> nodes[i].color; // 输入节点颜色
    }

    // 构建树
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        nodes[a].adj.push_back(b);
        nodes[b].adj.push_back(a);
    }

    // 存储所有好点的编号
    vector<int> goodNodes;
    // 标记节点是否被访问过
    vector<bool> visited(n + 1, false);

    // 深度优先搜索函数
    void dfs(int cur, int prevColor) {
        visited[cur] = true;
        // 判断当前节点是否为好点
        if (cur != 1 && nodes[cur].color != prevColor) {
            goodNodes.push_back(cur);
        }
        // 遍历当前节点的邻接节点
        for (int next : nodes[cur].adj) {
            if (!visited[next]) {
                dfs(next, nodes[cur].color);
            }
        }
    }

    // 从根节点开始深度优先搜索
    dfs(1, -1); // 初始颜色设置为 -1

    // 对好点集合进行排序
    sort(goodNodes.begin(), goodNodes.end());

    // 输出所有好点的编号
    for (int node : goodNodes) {
        cout << node << endl;
    }

    return 0;
}

代码优化建议：

可以使用 vector 的 resize 函数来预先分配好节点数组 nodes 的内存空间，避免在循环中多次进行内存分配，提高效率。
可以使用 map 存储颜色和节点编号的映射关系，以便在 dfs 函数中快速查找当前路径上是否出现过相同颜色的节点。
可以使用并查集来优化树的构建过程，将时间复杂度降低到 O(N)。

总结：

本文介绍了树上好点问题的求解方法，并给出了 C++ 代码实现。代码中包含了详细的注释，帮助读者理解代码逻辑。同时，还提供了一些代码优化建议，帮助读者进一步提高代码性能。希望本文能帮助读者更好地理解和解决树上好点问题。