There is a set of people represented as a uni-directional graph with no cycles.
Each person has a unique id.
If a person gets the virus, then every person reachable from that person through directed graph edges will also get the virus.
Given the graph and the id of one infected person, return all people who will get the virus.
Follow-up:
Instead of one id, now the input is a list of infected ids. Return all people who will get the virus with minimal changes in code.
Include the initially infected person or people in the returned result.
Return the final list of infected ids in ascending order.
Methods
List<Integer> infectedPeople(List<String> graph, int id)
graph is a list of directed edges- Each string in
graph is in the format "fromId,toId"
id is the unique id of the initially infected person- Return all unique infected person ids in ascending order
List<Integer> infectedPeopleFromIds(List<String> graph, List<Integer> ids)
graph is a list of directed edges- Each string in
graph is in the format "fromId,toId"
ids is the list of unique ids of initially infected people- Return all unique infected person ids in ascending order
Graph Representation
Each string in the directed graph contains exactly two integers separated by a comma:
"fromId,toId"
This means the virus can spread from person fromId to person toId.
Constraints
1 ≤ graph.size() ≤ 10^5- Each string in
graph is in the format "fromId,toId"
1 ≤ fromId, toId, id ≤ 10^91 ≤ ids.size() ≤ 10^5- All values in
ids are unique
- The graph is uni-directional
- The graph has no cycles
- Each person id is a unique human identifier
Notes
- A person infects every person reachable through one or more directed edges
- The starting infected person or people must be included in the answer
- If multiple starting ids can infect the same person, include that person only once
- Return ids in ascending order for deterministic output
Examples
Example 1
Method: infectedPeople
Input: graph = ["1,2", "1,3", "2,4", "3,5"], id = 1
Output: [1, 2, 3, 4, 5]
Explanation: Starting from person 1, the virus spreads to 2 and 3, then to 4 and 5.
Example 2
Method: infectedPeople
Input: graph = ["10,20", "20,30", "40,50"], id = 20
Output: [20, 30]
Explanation: Starting from person 20, the virus spreads only to 30. The edge "40,50" is not reachable.
Example 3
Method: infectedPeople
Input: graph = ["7,8", "8,9"], id = 9
Output: [9]
Explanation: Person 9 has no outgoing edge, so only 9 is infected.
Example 4
Method: infectedPeopleFromIds
Input: graph = ["1,2", "2,4", "3,5", "5,6"], ids = [1, 3]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Starting from 1, the virus reaches 2 and 4. Starting from 3, the virus reaches 5 and 6.
Example 5
Method: infectedPeopleFromIds
Input: graph = ["1,4", "2,4", "4,7", "7,8"], ids = [1, 2]
Output: [1, 2, 4, 7, 8]
Explanation: Both starting ids can reach person 4, but each infected id appears only once in the result.