统计树中的合法路径数目
难度:
标签:
题目描述
There is an undirected tree with n nodes labeled from 1 to n. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.
Return the number of valid paths in the tree.
A path (a, b) is valid if there exists exactly one prime number among the node labels in the path from a to b.
Note that:
- The path
(a, b)is a sequence of distinct nodes starting with nodeaand ending with nodebsuch that every two adjacent nodes in the sequence share an edge in the tree. - Path
(a, b)and path(b, a)are considered the same and counted only once.
Example 1:
Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]] Output: 4 Explanation: The pairs with exactly one prime number on the path between them are: - (1, 2) since the path from 1 to 2 contains prime number 2. - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (2, 4) since the path from 2 to 4 contains prime number 2. It can be shown that there are only 4 valid paths.
Example 2:
Input: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]] Output: 6 Explanation: The pairs with exactly one prime number on the path between them are: - (1, 2) since the path from 1 to 2 contains prime number 2. - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (1, 6) since the path from 1 to 6 contains prime number 3. - (2, 4) since the path from 2 to 4 contains prime number 2. - (3, 6) since the path from 3 to 6 contains prime number 3. It can be shown that there are only 6 valid paths.
Constraints:
1 <= n <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= n- The input is generated such that
edgesrepresent a valid tree.
代码结果
运行时间: 234 ms, 内存: 49.3 MB
// Java Stream Solution
// 思路：
// 1. 使用递归的方式进行深度优先搜索 (DFS) 遍历树。
// 2. 使用 Java Stream 进行集合操作来处理邻接节点的递归调用。
import java.util.*;
import java.util.stream.Collectors;
public class LegalPathCountStream {
private List<Integer>[] tree;
private boolean[] isPrime;
private boolean[] visited;
private int n;
private int legalPathCount;
public int countLegalPaths(int n, int[][] edges) {
this.n = n;
this.tree = new ArrayList[n + 1];
this.visited = new boolean[n + 1];
this.isPrime = new boolean[n + 1];
this.legalPathCount = 0;
// 初始化树结构
for (int i = 1; i <= n; i++) {
tree[i] = new ArrayList<>();
}
Arrays.stream(edges).forEach(edge -> {
tree[edge[0]].add(edge[1]);
tree[edge[1]].add(edge[0]);
});
// 预先标记所有质数
sieveOfEratosthenes(n);
// 从节点 1 开始 DFS 遍历
dfs(1, -1);
return legalPathCount;
}
private void sieveOfEratosthenes(int n) {
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
}
private void dfs(int node, int parent) {
visited[node] = true;
tree[node].stream()
.filter(neighbor -> neighbor != parent && !visited[neighbor])
.forEach(neighbor -> {
if (isPrime[node] && !isPrime[neighbor]) {
legalPathCount++;
}
dfs(neighbor, node);
});
}
}
// 使用示例
// LegalPathCountStream solution = new LegalPathCountStream();
// int result = solution.countLegalPaths(n, edges);解释
方法:
此题解采用了埃拉托斯特尼筛法来预处理质数，并使用并查集与图的邻接表来识别和处理路径。首先，通过筛法建立一个质数查找表PRIME，以便快速判断节点编号是否为质数。然后，遍历所有边，如果一条边的两个节点一个为质数一个非质数，则在图中添加这条边；如果两个节点都非质数，则通过并查集合并这两个节点。最后，计算图中每个联通分量的路径数量，只考虑含有质数节点的联通分量，使用组合公式计算每个联通分量中任意两点间路径的总数。
时间复杂度:
O(N log log N)
空间复杂度:
O(N)
代码细节讲解
🦆
题解中提到的`并查集`是如何在此问题的上下文中帮助合并非质数节点以及它的具体作用是什么？
▷🦆
为什么在处理图时只在一条边的两个节点一个为质数一个非质数的情况下添加这条边？如果两个节点都是质数怎么处理？
▷🦆
题解中使用了`埃拉托斯特尼筛法`预处理质数，能否解释一下这种筛法的原理以及为什么它是有效的？
▷🦆
计算联通分量中任意两点间路径的总数时使用了一个lambda函数`fn`，能否具体解释这个函数的计算逻辑及其如何应用于解题中？
▷