恰好有K个素数的子树

给定一棵有N 个节点和 (N – 1) 条边的树，其中节点的值从 1 到 N，根节点为 1。任务是确定给定树中是否存在恰好包含 K 的子树素数节点。

解决思路：

  • 使用深度优先搜索（DFS）来遍历树，计算每个子树中的素数节点。检查计数是否与 K 相等，如果找到，则答案设置为 true
  • 使用埃拉托斯特尼筛法来有效地识别素数。

什么是深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始（在图的情况下选择某个任意节点作为根节点），并在回溯之前沿着每个分支尽可能远地探索。

图的深度优先遍历（或 DFS）类似于树的深度优先遍历。这里唯一的问题是，与树不同，图可能包含循环（一个节点可能被访问两次）。为了避免多次处理节点，请使用布尔访问数组。一张图可以有多个 DFS 遍历。

树遍历技术：
与只有一种逻辑方式来遍历它们的线性数据结构（数组、链表、队列、堆栈等）不同，树可以用不同的方式来遍历。 
树形数据结构可以通过以下方式遍历：

  1. 深度优先搜索或 DFS[list=1]
  2. 中序遍历
  3. 预序遍历
  4. 后序遍历
  • 层序遍历或广度优先搜索或 BFS
  • 边界遍历
  • 对角线遍历


    分步算法：

    • 为树创建一个邻接列表adj并初始化一个从 0 到 n 的素数列表素数，使用埃拉托斯特尼筛法将 0 和 1 标记为非素数。
    • 定义一个 DFS 函数 (DFS(node, adj, prime, vis, ans, k))，将当前节点标记为已访问，计算其子树中的素节点数，如果计数等于 k，则递增 ans。
    • 对当前节点的未访问邻居递归调用该函数。
    • 初始化访问列表 vis 和答案列表 ans，并为根节点（例如节点 1）调用 DFS。
    • 检查ans列表中的值是否大于0，如果大于则返回true，否则返回false。

    C++代码：

    include <bits/stdc++.h>
    using namespace std;

    // Function to start iterating from node 1
    int dfs(int node, vector<vector<int> >& adj,
            vector<bool>& prime, vector<int>& vis, int& ans,
            int K)
    {

        if (ans > 0)
            return 0;

        // If node is visited
        vis[node] = 1;

        int ele = 0;

        // 如果节点是质数
        if (prime[node])
            ele += 1;

        // 进一步迭代到其相邻节点
        for (auto j : adj[node]) {
            if (vis[j] == 0) {
                ele += dfs(j, adj, prime, vis, ans, K);
            }
        }

        //如果质数总数为 K
        if (ele == K) {
            ans += 1;
        }

        // Return ele
        return ele;
    }

    //查找树是否有
    // K 素子集的函数
    bool hasKPrimeSubtree(int N, int K,
                        vector<vector<int> >& edges)
    {
        // 创建邻接矩阵
        vector<vector<int> > adj(N + 1, vector<int>());

        //边缘迭代
        for (auto j : edges) {

            int u = j[0];
            int v = j[1];
            adj.push_back(v);
            adj[v].push_back(u);
        }

        //创建质数向量
        vector<bool> prime(N + 1, 1);

        //因为 0 和 1 都不是质数
        prime[0] = prime[1] = false;

        //填充质数向量
        for (int p = 2; p * p <= N; ++p) {
            if (prime[p] == true) {
                for (int i = p * p; i <= N; i += p)
                    prime = false;
            }
        }

        // 检查已访问元素的向量
        vector<int> vis(N + 1, 0);
        int ans = 0;

        // 开始在树中迭代的函数
        int ele = dfs(1, adj, prime, vis, ans, K);
        return (ans > 0);
    }

    // Driver code
    int main()
    {

        int N = 3;
        int K = 1;
        vector<vector<int> > edges = { { 1, 3 }, { 1, 2 } };

        // Function call
        cout << hasKPrimeSubtree(N, K, edges);
        return 0;
    }

    时间复杂度： O(N * log(log(N)))，其中N是树中的节点数。
    辅助空间： O(N)