2581. Count Number of Possible Root Nodes LeetCode Solution
In this guide, you will get 2581. Count Number of Possible Root Nodes LeetCode Solution with the best time and space complexity. The solution to Count Number of Possible Root Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Number of Possible Root Nodes
Alice has an undirected tree with n nodes labeled from 0 to n – 1. The tree is represented as a 2D integer array edges of length n – 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Alice wants Bob to find the root of the tree. She allows Bob to make several guesses about her tree. In one guess, he does the following:
Chooses two distinct integers u and v such that there exists an edge [u, v] in the tree.
He tells Alice that u is the parent of v in the tree.
Bob’s guesses are represented by a 2D integer array guesses where guesses[j] = [uj, vj] indicates Bob guessed uj to be the parent of vj.
Alice being lazy, does not reply to each of Bob’s guesses, but just says that at least k of his guesses are true.
Given the 2D integer arrays edges, guesses and the integer k, return the number of possible nodes that can be the root of Alice’s tree. If there is no such tree, return 0.
Input: edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
Output: 5
Explanation:
Root = 0, correct guesses = [3,4]
Root = 1, correct guesses = [1,0], [3,4]
Root = 2, correct guesses = [1,0], [2,1], [3,4]
Root = 3, correct guesses = [1,0], [2,1], [3,2], [3,4]
Root = 4, correct guesses = [1,0], [2,1], [3,2]
Considering any node as root will give at least 1 correct guess.
Constraints:
edges.length == n – 1
2 <= n <= 105
1 <= guesses.length <= 105
0 <= ai, bi, uj, vj <= n – 1
ai != bi
uj != vj
edges represents a valid tree.
guesses[j] is an edge of the tree.
guesses is unique.
0 <= k <= guesses.length
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2581. Count Number of Possible Root Nodes LeetCode Solution in C++
class Solution {
public:
int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses,
int k) {
int ans = 0;
const int n = edges.size() + 1;
vector<vector<int>> graph(n);
vector<unordered_set<int>> guessGraph(n);
vector<int> parent(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
for (const vector<int>& guess : guesses) {
const int u = guess[0];
const int v = guess[1];
guessGraph[u].insert(v);
}
// Precalculate `parent`.
dfs(graph, 0, /*prev=*/-1, parent);
// Calculate `correctGuess` for tree rooted at 0.
int correctGuess = 0;
for (int i = 1; i < n; ++i)
if (guessGraph[parent[i]].contains(i))
++correctGuess;
reroot(graph, 0, /*prev=*/-1, correctGuess, guessGraph, k, ans);
return ans;
}
private:
void dfs(const vector<vector<int>>& graph, int u, int prev,
vector<int>& parent) {
parent[u] = prev;
for (const int v : graph[u])
if (v != prev)
dfs(graph, v, u, parent);
}
void reroot(const vector<vector<int>>& graph, int u, int prev,
int correctGuess, const vector<unordered_set<int>>& guessGraph,
const int& k, int& ans) {
if (u != 0) {
// The tree is rooted at u, so a guess edge (u, prev) will match the new
// `parent` relationship.
if (guessGraph[u].contains(prev))
++correctGuess;
// A guess edge (prev, u) matching the old `parent` relationship will no
// longer be true.
if (guessGraph[prev].contains(u))
--correctGuess;
}
if (correctGuess >= k)
++ans;
for (const int v : graph[u])
if (v != prev)
reroot(graph, v, u, correctGuess, guessGraph, k, ans);
}
}; /* code provided by PROGIEZ */
2581. Count Number of Possible Root Nodes LeetCode Solution in Java
class Solution {
public int rootCount(int[][] edges, int[][] guesses, int k) {
final int n = edges.length + 1;
List<Integer>[] graph = new List[n];
Set<Integer>[] guessGraph = new Set[n];
int[] parent = new int[n];
for (int i = 0; i < n; ++i) {
graph[i] = new ArrayList<>();
guessGraph[i] = new HashSet<>();
}
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
for (int[] guess : guesses) {
final int u = guess[0];
final int v = guess[1];
guessGraph[u].add(v);
}
// Precalculate `parent`.
dfs(graph, 0, /*prev=*/-1, parent);
// Calculate `correctGuess` for tree rooted at 0.
int correctGuess = 0;
for (int i = 1; i < n; ++i)
if (guessGraph[parent[i]].contains(i))
++correctGuess;
reroot(graph, 0, /*prev=*/-1, correctGuess, guessGraph, k);
return ans;
}
private int ans = 0;
private void dfs(List<Integer>[] graph, int u, int prev, int[] parent) {
parent[u] = prev;
for (final int v : graph[u])
if (v != prev)
dfs(graph, v, u, parent);
}
private void reroot(List<Integer>[] graph, int u, int prev, int correctGuess,
Set<Integer>[] guessGraph, int k) {
if (u != 0) {
// The tree is rooted at u, so a guess edge (u, prev) will match the new
// `parent` relationship.
if (guessGraph[u].contains(prev))
++correctGuess;
// A guess edge (prev, u) matching the old `parent` relationship will no
// longer be true.
if (guessGraph[prev].contains(u))
--correctGuess;
}
if (correctGuess >= k)
++ans;
for (final int v : graph[u])
if (v != prev)
reroot(graph, v, u, correctGuess, guessGraph, k);
}
} // code provided by PROGIEZ
2581. Count Number of Possible Root Nodes LeetCode Solution in Python
class Solution:
def rootCount(
self,
edges: list[list[int]],
guesses: list[list[int]],
k: int,
) -> int:
ans = 0
n = len(edges) + 1
graph = [[] for _ in range(n)]
guessGraph = [set() for _ in range(n)]
parent = [0] * n
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
for u, v in guesses:
guessGraph[u].add(v)
def dfs(u: int, prev: int) -> None:
parent[u] = prev
for v in graph[u]:
if v != prev:
dfs(v, u)
# Precalculate `parent`.
dfs(0, -1)
# Calculate `correctGuess` for tree rooted at 0.
correctGuess = sum(i in guessGraph[parent[i]] for i in range(1, n))
def reroot(u: int, prev: int, correctGuess: int) -> None:
nonlocal ans
if u != 0:
# The tree is rooted at u, so a guess edge (u, prev) will match the new
# `parent` relationship.
if prev in guessGraph[u]:
correctGuess += 1
# A guess edge (prev, u) matching the old `parent` relationship will no
# longer be True.
if u in guessGraph[prev]:
correctGuess -= 1
if correctGuess >= k:
ans += 1
for v in graph[u]:
if v != prev:
reroot(v, u, correctGuess)
reroot(0, -1, correctGuess)
return ans # code by PROGIEZ
