Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- private Map<Integer, List<Integer>> graph;
- private List<Integer> a;
- private int c;
- private int dfs(int node, int goodCount) {
- if (this.a.get(node - 1) == 1) {
- goodCount++;
- }
- if (goodCount > this.c) {
- return 0;
- }
- if (this.graph.get(node).isEmpty() && node != 1) {
- return 1;
- }
- var pathCount = 0;
- List<Integer> neighbors = new ArrayList<>(this.graph.get(node));
- for (var neighbor : neighbors) {
- this.graph.get(neighbor).remove((Integer) node);
- pathCount += dfs(neighbor, goodCount);
- }
- return pathCount;
- }
- /**
- * This method counts the number of root to leaf paths in a tree
- * that contain not more than a given number of good nodes.
- * <p>
- * Time Complexity: O(N) - where N is the number of nodes in the tree.
- * Every node and edge is visited once.
- * <p>
- * Space Complexity: O(N) - for storing the graph and the recursion call stack.
- *
- * @param a Binary List representing good (1) and bad (0) nodes.
- * @param b List of List of Integer representing edges of the tree.
- * @param c Maximum number of good nodes allowed in a root to leaf path.
- */
- public int solve(List<Integer> a, List<List<Integer>> b, int c) {
- this.a = a;
- this.c = c;
- this.graph = new HashMap<>();
- for (var i = 0; i < a.size(); i++) {
- this.graph.put(i + 1, new ArrayList<>());
- }
- for (var edge : b) {
- this.graph.get(edge.get(0)).add(edge.get(1));
- this.graph.get(edge.get(1)).add(edge.get(0));
- }
- return dfs(1, 0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
