#690

Employee Importance

specialist · 625 · lc medium +29 · verified · 69.3% accepted · 2,206 likes · top 77%

⚑ DFS / BFS: Connected Components & Reachability

Description

Each employee has a unique ID, an importance score, and a list of direct subordinate IDs. You are given an array employees where:

- employees[i].id is the unique identifier of the i^th employee.

- employees[i].importance is the importance score of the i^th employee.

- employees[i].subordinates lists the IDs of the i^th employee's direct reports.

Given an integer id, return the cumulative importance score of that employee plus all of their subordinates, direct and indirect.

Example 1:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1

Output: 11

Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.

They both have an importance value of 3.

Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

Example 2:

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5

Output: -3

Explanation: Employee 5 has an importance value of -3 and has no direct subordinates.

Thus, the total importance value of employee 5 is -3.

Code

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int: