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:
u and v such that there exists an edge [u, v] in the tree.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.
Example 1:
Input: edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3 Output: 3 Explanation: Root = 0, correct guesses = [1,3], [0,1], [2,4] Root = 1, correct guesses = [1,3], [1,0], [2,4] Root = 2, correct guesses = [1,3], [1,0], [2,4] Root = 3, correct guesses = [1,0], [2,4] Root = 4, correct guesses = [1,3], [1,0] Considering 0, 1, or 2 as root node leads to 3 correct guesses.
Example 2:
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 - 12 <= n <= 1051 <= guesses.length <= 1050 <= ai, bi, uj, vj <= n - 1ai != biuj != vjedges represents a valid tree.guesses[j] is an edge of the tree.guesses is unique.0 <= k <= guesses.lengthThis approach involves building the tree and performing a Depth-First Search (DFS) from an arbitrary node, usually node 0, to determine the initial configuration or parent-child relationships. By maintaining awareness of which guesses match the found parent-child relationships, you can compute the number of valid roots by rerooting the tree at each node.
The C implementation uses basic adjacency matrix to represent the tree graph. DFS is implemented to explore and calculate valid guesses for each node treated as the root. The counter is incremented when a node u and its child v is correctly guessed according to the given guesses. Resetting the visited array and guess count for each node ensures correctness.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of nodes. This results from the DFS implementation using an adjacency matrix, which inefficiently checks each potential connection.
Space Complexity: O(n^2), due to the adjacency matrix used for graph representation.
This approach utilizes the Union-Find data structure to keep track of connected components in an efficient way—each node as its own separate component and merging them via edges. By adapting the structure for parent relationships and examining which parent associations hold true, we can determine potential roots that meet the guessing criteria.
The Union-Find approach involves an initial setup of disjoint sets with each node as its own component. Union operations merge components represented by the edges. For guesses, their validity is checked by finding their roots, allowing accumulation of correct guess counts. Nodes with a correct count greater than or equal to k will be marked as valid roots.
Python
Time Complexity: O(n*α(n)), where α is the inverse Ackermann function, due to the efficient union-find operations.
Space Complexity: O(n), for storing parent and rank arrays.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) with Rooted Tree | Time Complexity: O(n^2), where n is the number of nodes. This results from the DFS implementation using an adjacency matrix, which inefficiently checks each potential connection. Space Complexity: O(n^2), due to the adjacency matrix used for graph representation. |
| Using Union-Find (Disjoint Set Union, DSU) | Time Complexity: O(n*α(n)), where α is the inverse Ackermann function, due to the efficient union-find operations. |
L32. Count total Nodes in a COMPLETE Binary Tree | O(Log^2 N) Approach | C++ | Java • take U forward • 147,880 views views
Watch 9 more video solutions →Practice Count Number of Possible Root Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor