恰好有K个素数的子树
给定一棵有N 个节点和 (N – 1) 条边的树,其中节点的值从 1 到 N,根节点为 1。任务是确定给定树中是否存在恰好包含 K 的子树素数节点。
解决思路:
- 使用深度优先搜索(DFS)来遍历树,计算每个子树中的素数节点。检查计数是否与 K 相等,如果找到,则答案设置为 true
- 使用埃拉托斯特尼筛法来有效地识别素数。
什么是深度优先搜索(DFS)
深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始(在图的情况下选择某个任意节点作为根节点),并在回溯之前沿着每个分支尽可能远地探索。
图的深度优先遍历(或 DFS)类似于树的深度优先遍历。这里唯一的问题是,与树不同,图可能包含循环(一个节点可能被访问两次)。为了避免多次处理节点,请使用布尔访问数组。一张图可以有多个 DFS 遍历。
树遍历技术:
与只有一种逻辑方式来遍历它们的线性数据结构(数组、链表、队列、堆栈等)不同,树可以用不同的方式来遍历。
树形数据结构可以通过以下方式遍历:
- 深度优先搜索或 DFS[list=1]
- 中序遍历
- 预序遍历
- 后序遍历
分步算法:
- 为树创建一个邻接列表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)