221. Validate Organization Reporting Structure

Validate Organization Reporting Structure

You are given a reporting structure of people in an organization. Each entry is a string in the format "employee,manager", meaning the employee directly reports to the manager.

Determine whether the reporting structure forms one valid organization. A valid organization must satisfy all of the following rules:

All people must belong to the same organization.
No person can report to themselves.
There must be exactly one head of the organization.
Every non-head person must directly or indirectly report to the head.
A person cannot have more than one direct manager.
The reporting structure must not contain any cycle.

As a follow-up, for a given manager, return how many people directly or indirectly report to that manager.

Method Signatures

Validate Organization

boolean isValidOrganization(List<String> reports)

reports: a list of reporting relations.
Each string is in the format "employee,manager".
Return true if all reporting relations form one valid organization.
Return false otherwise.

Count Reports To Manager

int countReportsToManager(List<String> reports, int managerId)

reports: a list of reporting relations.
managerId: the manager whose report count is requested.
Count both direct and indirect reports.
If the organization is invalid, return -1.
If the organization is valid but managerId does not exist, return 0.

Definitions

The head of the organization is a person who does not report to anyone.
A direct report is an employee immediately connected to a manager.
An indirect report is an employee connected through one or more reporting levels.

Constraints

1 ≤ reports.size() ≤ 200,000
1 ≤ employee ≤ 1,000,000,000
1 ≤ manager ≤ 1,000,000,000
Each string in reports contains exactly two positive integers separated by a comma.
1 ≤ managerId ≤ 1,000,000,000
All reporting strings are unique.

Examples

Example 1

isValidOrganization(reports = ["2,1", "3,1", "4,2", "5,2"])

Output: true

Explanation: Person 1 is the only head, and every other person reports directly or indirectly to person 1.

Example 2

countReportsToManager(reports = ["2,1", "3,1", "4,2", "5,2"], managerId = 2)

Output: 2

Explanation: People 4 and 5 directly report to manager 2.

Example 3

isValidOrganization(reports = ["2,1", "4,3"])

Output: false

Explanation: There are two separate organization heads, 1 and 3, so all people are not part of the same organization.

Example 4

isValidOrganization(reports = ["2,1", "3,2", "1,3"])

Output: false

Explanation: The reporting structure contains a cycle, so there is no valid single head.

Example 5

countReportsToManager(reports = ["2,1", "3,1", "4,2", "5,4"], managerId = 1)

Output: 4

Explanation: People 2, 3, 4, and 5 directly or indirectly report to manager 1.

Example 6

countReportsToManager(reports = ["2,2", "3,1"], managerId = 1)

Output: -1

Explanation: Person 2 reports to themselves, so the organization is invalid.