Employee Hierarchy

Build a company tree and compute each employee's direct and indirect report count.

tree dfs graph recursion

You are given a list of employee relationships. Each element in the list is a tuple `(manager, employee)` indicating that `manager` is the direct manager of `employee`. Managers and employees are represented by strings. An employee can have at most one direct manager. One employee has no manager; that is the CEO (root).

Implement a function `report_counts(relationships)` that returns a dictionary mapping each employee's name to the total number of employees directly or indirectly reporting to them. That is, for each employee, count all descendants in the company tree. The result should include all employees that appear in any relationship (both managers and employees). The CEO should have the total number of employees except the CEO. An employee with no direct reports should have a count of 0.

The input list may be empty, in which case return an empty dictionary.

**Function signature:**
```python
def report_counts(relationships: list[tuple[str, str]]) -> dict[str, int]:
```

Constraints

`0 <= len(relationships) <= 10^4`
All names are non-empty strings of lowercase letters, at most 20 characters.
No cycles in the hierarchy; every employee has at most one direct manager.
The input is a valid tree (one root) when non-empty.

Example

```python
>>> report_counts([("Alice", "Bob"), ("Bob", "Carol")])
{'Alice': 2, 'Bob': 1, 'Carol': 0}
>>> report_counts([("CEO", "VP"), ("CEO", "Dev"), ("VP", "Intern")])
{'CEO': 3, 'VP': 1, 'Dev': 0, 'Intern': 0}
>>> report_counts([])
{}
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build a mapping from manager to list of direct reports.

Use recursion or iterative post-order traversal to compute the size of each subtree.

The count for an employee is the sum of the counts of their direct reports plus the number of direct reports.

Be careful to include all employees, even those with no direct reports (count 0).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.