#2581

Count Number of Possible Root Nodes

candidate master · 1480 · lc hard +32 · verified · 48.1% accepted · 322 likes · top 34%

Description

Alice has an undirected n-node tree (nodes 0 to n-1) described by edges. Bob makes guesses guesses[j] = [uj, vj] asserting that uj is the parent of vj. Alice only confirms that at least k guesses are correct. Given edges, guesses, and k, return the number of nodes that could be the actual root of the tree, or 0 if none exist.

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.

Code

1

2

3

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int: